单调栈数组问题——每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

单调栈的基本思想是，维护一个栈，栈内的元素从栈底到栈顶保持单调递增或者递减的顺序。在元素入栈时，如果破坏了单调递增或者递减的顺序，就进行一些操作使得重新满足单调递增/减条件。
单调递增栈步骤：

遍历数组或序列的元素。
对于每个元素，进行如下操作：
    如果栈为空，直接将当前元素入栈。
    如果栈不为空，比较当前元素与栈顶元素的大小：
        如果当前元素小于等于栈顶元素，直接入栈。
        如果当前元素大于栈顶元素，不断弹出栈顶元素，直到当前元素小于等于栈顶元素，然后将当前元素入栈。

单调递增栈常用于解决一些与查找下一个更大元素相关的问题，例如：

• 下一个更大元素： 对于数组中的每个元素，找到数组中右边第一个比它大的元素的位置。 柱状图中的最大矩形面积：
• 给定柱状图的高度数组，找到能够组成的最大矩形的面积。
• 接雨水问题： 给定一个数组，表示每个位置的高度，计算这个地形能够存储多少雨水。

回到本题：这题就是经典的单调栈题目。
思路：维护一个递减栈。由于每一次我们都需要知道后面一个较大的值，那么首先遍历数组，如果数是递减的就不断压栈，如果出现了当前数比栈顶的数大的就说明了——栈里面一定可以有至少一个元素能找到较大数字的下标，把满足条件的全部移出栈并更新答案数组即可。
代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0 ; i< temperatures.length;i++){
            if(stack.size()==0){
                stack.addFirst(i);
            }else{
                int peekFirst = stack.peekFirst();
                if(temperatures[i]<=temperatures[peekFirst]){
                    stack.addFirst(i);
                }else{
                    while(stack.size()!=0&&temperatures[stack.peekFirst()]<temperatures[i]){
                        int k = stack.removeFirst();
                        //这里算的是差，而不是下标
                        ans[k] = i-k;
                    }
                }
                //处理完别忘了再把这个数也压栈
                stack.addFirst(i);
            }
        }
        //把后面没有最高温度的统一置零
        while(stack.size()!=0){
            int k = stack.removeFirst();
            ans[k] = 0;
        }
        return ans;
    }
}

我们考虑优化代码，发现里面有很多冗余的地方，我们发现很多特判完了都只是做了压栈的操作，那么把这一步单独拉出来，把出栈判断就行了。还有就是最后的置0也是多余的，java会初始化数组为0。
优化后的代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0 ; i< temperatures.length;i++){
            while(stack.size()!=0&&temperatures[stack.peekFirst()]<temperatures[i]){
                int k = stack.removeFirst();
                //这里算的是差，而不是下标
                ans[k] = i-k;
            }
            stack.addFirst(i);
        }
        //把后面没有最高温度的统一置零
        // while(stack.size()!=0){
        //     int k = stack.removeFirst();
        //     ans[k] = 0;
        // }
        //上面这一步需要吗，不需要啊，JVM初始化就是0，还管他干嘛呢？
        return ans;
    }
}