单调栈

说明：

题目推荐：131. 直方图中最大的矩形 - AcWing题库

Java简单单调栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class 单调栈 {
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		
	
		Stack<Integer>s=new Stack<Integer>();
		
		for(int i=0;i<n;i++) {
			int x=sc.nextInt();
		
			
			while(!s.isEmpty() && s.peek() >= x) 
				s.pop();
			
			if(s.isEmpty())
				System.out.print("-1 ");
			else 
				System.out.print(s.peek()+" ");
			
			s.push(x);
		}
//		5
//		3 4 2 7 5
//		大于x的数出栈 小于x的数输出
//		输出  -1 3 -1 2 2 
	}
}