数据结构——单调栈

单调栈

单调栈可以用来优化
最常用的情景：给定一个序列，找到序列每一个数左边离它最近且比他小的数

题目

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。
3 4 2 7 5
-1 3 -1 2 2

结论：我们用栈存储一列升序的数，取栈顶即可，当添加一个数时，也必须保证升序，将比他大的删除，即tt–

题解

模板

import java.io.*;
/**
 * P830 单调栈
 * @author vccyb
 *
 */
public class Main {
	private static final int N = 100010;
	private static int[] stk = new int[N];
	private static int tt = -1; //栈顶
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		String[] line = br.readLine().split(" ");
		
		for(int i=0;i<n;i++){
			int x = Integer.parseInt(line[i]);
			//入栈 必须是升序的  找到左边第一个比x小的
			while(tt!=-1&&stk[tt]>=x){
				tt--;
			}
			
			if(tt!=-1){
				bw.write(stk[tt]+" ");
			}else{
				bw.write("-1 ");
			}
			
			stk[++tt] = x; //加进来后还是升序的
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

大家可以根据模板自行想求解每个数左边第一个比它大的数