AcWing 830. 单调栈(JAVA)
原题链接
简单
作者:
鼠鼠我
,
2021-01-29 20:34:11
,
所有人可见
,
阅读 225
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
//一般用单调栈求出左边/右边离他最近的数的最小/最大值/第一个比他小/大的元素
static int skt[];
static int N = 100010;
static int tail;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
skt = new int[N];
String s[] = br.readLine().split("\\s+");
int n = Integer.parseInt(s[0]);
String ss[] = br.readLine().split("\\s+");
for(int i=0;i<n;i++)
{
int x = Integer.parseInt(ss[i]);
while(tail>0 && x<=skt[tail]) tail--;//当栈存在且当前数值小于栈尾元素(也就是离他最近的一个元素)
if(tail>0) System.out.print(skt[tail]+" ");
else {
System.out.print(-1+" ");
}
skt[++tail] = x;
}
}
}