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

2023-12-26 15:49:21

题目链接: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;
    }
}

文章来源:https://blog.csdn.net/qq_45816864/article/details/135221486
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。