模板
常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i < n; i ++ )
{
while (tt > 0 && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
方法一:更符合y总的写法
import java.util.Scanner;
public class Main{
private static int N = 100010;
private static int tt = 0; //栈顶
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] stk = new int[N]; //数组模拟栈
for(int i = 0; i < n; i ++)
{
int x = in.nextInt();
while(tt > 0 && stk[tt] >= x) tt--; //这行代码很巧,后面再说
if(tt > 0) System.out.print(stk[tt] + " "); //输出结果
else System.out.print("-1 ");
stk[++tt] = x; //当前值入栈
}
}
}
方法二 :用到了java中的Stack类
import java.util.Scanner;
import java.util.Stack;
public class Main{
private static int N = 100010;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[N];
for(int i = 0;i < n; i ++) a[i] = in.nextInt();
Stack<Integer> stk = new Stack<>();
for(int i = 0; i < n; i ++){
while(!stk.isEmpty() && stk.peek() >= a[i]) stk.pop();
if(!stk.isEmpty()) System.out.print(stk.peek() + " ");
else System.out.print("-1 ");
stk.push(a[i]);
}
}
}
我们可以看出来两种方法极其的相似,我们那第一种方法为例
1:while(tt > 0 && stk[tt] >= x) tt--;
最核心的代码就是这一行,这行代码有两种作用
1:维护一个单调递增的栈
当左边的数比当前值x大的时候,就把他去除,这样就保证了左边的数永远比当前数小,然后花在x,y轴上的时候,就会单调递增的
2:在寻找左边小于x的第一个元素的时候,去除栈顶没有用的元素,左边的数比当前值x大,这个左边的数就永远不会用到了,因为本题找的是左边第一个小于当前数的,然后我们的for循环是从左向右循环,然后右边的数找的话也是找x,而不是更左边