单调栈

单调栈

情景： 最常用：给定一个序列，找到序列每一个数左边离它最近且比他小的数

例如：

• 3 4 2 7 5

• -1 3 -1 2 2

思路：一般先找暴力做法，然后优化

优化的思路：可以用一个栈来存储，

1. a_3 a_5 a_i
2. 假设 a_3 >= a_5
3. a_3 一定不会输出， 为何？ a_5 更接近a_i, 如果a_3小于a_i,a_5必小于a_i，输出为a_5

所以栈存储的是单调，上升的一列数

输入stk的最后一个元素即可了

模板

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

题目

AcWing

• 830 单调栈

Ac830 单调栈

描述

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

解答

import java.util.*;
import java.io.*;
public class Main {
	static final int N = 100010;
    static int[] stk = new int[N];
    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[] s = br.readLine().split(" ");
        
        //
        for(int i=0;i<n;i++){
        	int x = Integer.parseInt(s[i]);
        	
            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();
    }
}

图解

注意：由于接受上升的数据，所以，如果之前有比a_i 大的，全部删除，对应的代码就是

while(tt!=-1&&stk[tt]>=x){
	tt--;
}

删除完了，判断下是否栈是空的，
是就输出-1，没有比它小的数
否，输出stk[tt]即可

最后一步就是新元素入栈

Others

人无完人，何况是小白Chen我呢，文章难免会出现一些错误，若是读者们发现错误，可以评论或者联系我，Chen会尽力改正，给大家更优秀的博文。