单调栈类似于双指针：先暴力，再聚焦在比较少的状态之内，去发现一些性质，就优化了时间。

基本考察的模型/提醒，ai左边/右边比它大/小的数，这样的一个性质。

经典模型：给定一个序列，每一个数左边离它最近最小/大数，或者右边最近最小/大的数。

板子题目：830.单调栈

习题

830.单调栈

思想：

• 暴力解法：当前ai找到一个离它最近而且小的数量，那就是如下代码。

for(int i = 0;i < n;i++) {
    for(int j = i - 1;j >= 0;j--){
        if(a[j] < a[i]) break;
    }
}

• 那我们想如果要将数存到一个数据结构中，并且是能够获取离i近的。很明显可以用栈存：后进先出离得近。
• 再优化：会发现性质：有些数，是不是可能用于不会用到，那就不需要存到里面。

如果当前元素是符合需求的：小且最近，那么直接弹出栈顶即可。

如果不是，那么就是st[tt] >= x，举例当前是 a3 >= a5.

如果对于x = ai，如果a3满足是，a3 < ai；那么a5 < ai。所以a5一定比a3要好，即对于ax >= ay(x < y)这样的逆序对。

ay 好于 ax，那么这样的就没有必要存进栈中了。也就构成了单调递增的一个状态。

a3 >= a5 < ai

得到这样的一个图，那么这里的 1 这个点就没必要存在了，因为2更好，所以把这样逆序的点都删掉。那么，求左边比它小的数，就成了一个单调递增序列。

import java.util.*;

public class Main {

    static int N = 100010;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] st = new int[N];
        int tt = -1;

        for(int i = 0;i < n;i++) {
            int x = sc.nextInt();

            while(tt != -1 && st[tt] >= x) tt--;

            if(tt != -1) System.out.print(st[tt] + " ");
            else System.out.print("-1 ");

            st[++tt] = x;
        }
    }
}

• 为什么使用while呢？

比如例子3 5 2 7 5答案-1 3 -1 2 2

这里在考虑2时，对于5考虑完并且弹出之后，还有3呢，所以防止弹出之后的栈顶依然不满足要求，得用while循环弹出。

739.每日温度

所以，该题就是这样解的，那么就需要翻转结果，最终自己写一个翻转函数即可。

• 分析：时间O（n），空间O（n）

class Solution {
    int tt = -1;
    int N = 100010;
    int[] st = new int[N];
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];

        for(int i = n - 1;i >= 0;i--) {
            while(tt != -1 && temperatures[i] > temperatures[st[tt]]) tt--;
            if(tt != -1) res[i] = Math.abs(i - st[tt]);
            else res[i] = 0;
            st[++tt] = i;
        }

        return reverse(res);
    }

    private int[] reverse(int[] nums) {
        for(int i = 0;i < nums.length;i++) {
            int tmp = nums[i];
            nums[i] = nums[nums.length - i - 1];
            nums[nums.length - i - 1] = tmp;
        }
        return nums;
    }
}

总结

总结规律：
从考虑有些元素是没必要存进栈里的角度出发
● 求左边最近最小，那么从左往右遍历，那么后边比前面栈顶的好，就没必要存
● 求右边最近最大，那么从右往左遍历，那么前边比后面栈顶的好，就没必要存
也就是说，看怎么能利用这个角度去解题。

如果是这样的话：
  ○ 求左边最近最大，从左到右
  ○ 求右边最近最小，从右到左遍历
简化：
  ○ 求左边的，从左往右遍历
  ○ 求右边的，从右往左遍历
都是为了适应：没必要存进栈里这一点。