【算法】单单单单单调栈，接接接接接雨水

今天没有小故事。

参考以及题单来源：

代码随想录 (programmercarl.com)

Part 1 啥是单调栈？

1.啥啥啥是单调栈？

栈的特性想必各位再熟悉不过了：先进后出。栈仅仅有一个出口，故而先进入的会被压到栈底，而想取出元素时，则必须从栈顶开始取。

而单调栈，就是在入栈的时候加了一则限制条件：

入栈的元素必须大于（或者小于）栈顶元素，否则弹出栈顶元素，直到满足条件再压入新元素，从而使得栈内元素满足单调递增或者单调递减的规律。

2.这这这是单调栈！

光说不画假把戏，上图！

此处以单调递增栈为例：

QQ图片20240404205420

Part 2 现在你已经完全学会了单调栈，那我们来试试题吧！.JPG

503.下一个更大元素 ||

原题链接：

503. 下一个更大元素 II - 力扣（LeetCode）

寻找下一个更大元素，只需要套用单调栈的模板即可，唯一的不同在于，这里在一个循环数组中寻找对应元素，也很简单，将同样的两个链表拼接在一起（模拟遍历一圈）再求值即可。

值得注意的是，由于将两个链表拼接在了一起，ans数组的大小就不好确定，这里将迭代器中的每个i都用数组大小取模，解决了这个问题。

if(!st.isEmpty() && nums[st.peek()] < nums[i % lens]){
    while(!st.isEmpty() && nums[st.peek()] < nums[i % lens]){
        ans[st.peek()] = nums[i % lens];
        st.pop();
    }
    st.push(i % lens);
}else{
    st.push(i % lens);
}

同时，如果不存在想寻找的数字，则输出-1，由于这条规则，我们调用fill方法，将数组初始化为-1。

Arrays.fill(ans,-1);

AC代码如下：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> st = new Stack<>();
        int lens = nums.length;
        int[] ans = new int[lens];
        Arrays.fill(ans,-1);
        //遍历两次数组，同时对i取模，模拟循环遍历
        for(int i = 0;i < lens*2;++i){
            //单调栈模板~猛猛套用
            //下一个最大元素，故而维护栈底到栈顶单调递减
            if(!st.isEmpty() && nums[st.peek()] < nums[i % lens]){
                while(!st.isEmpty() && nums[st.peek()] < nums[i % lens]){
                    ans[st.peek()] = nums[i % lens];
                    st.pop();
                }
                st.push(i % lens);
            }else{
                st.push(i % lens);
            }
        }
        return ans;
    }
}
//执行用时过高，但代码时间复杂度已经较低。初步判断可能是new对象导致、
//在较低执行用时的题解中发现有人用Array实现的Deque双端队列，同样的思路但其时间复杂度较低，可能是底层框架的问题。

739.每日温度

原题链接：

739. 每日温度 - 力扣（LeetCode）

这道题仍然可以通过遍历解决，但遍历的方式显然时间复杂度过高（比上题还高），所以这道题试着使用单调栈来解决。

维护一个单调栈，如果发现小于栈顶元素则入栈，发现大于栈顶元素，就相当于找到了下一个更大的元素，则将栈顶元素出栈，再把新的元素入栈，每出一个元素，就相当于找到了一个更大的元素。

值得一提的是其中一句Arrays.fill这句代码，将答案数组全部元素填充为0，表示气温如果没有升高的情况，则用0代替。（虽然在java中数组默认的初始值都是0）

Arrays.fill(ans,0);

AC代码如下：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> st = new Stack<>();
        int len = temperatures.length;
        int[] ans = new int[len];
        Arrays.fill(ans,0);
        for(int i = 0;i < len;++i){
            if(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){
                //如果大于栈顶元素则出栈，并维护栈的单调递增（由顶到底）
                while(!st.isEmpty()&&temperatures[i]>temperatures[st.peek()]){
                    ans[st.peek()]=i-st.peek();
                    st.pop();
                }
                st.push(i);
            }else{
                //如果发现小于等于栈顶元素则入栈
                st.push(i);
            }
        }
        return ans;
    }
}
//Tip：题解中时间复杂度较低的答案，使用数组模拟栈进行操作。

42.接雨水

原题链接：

42. 接雨水 - 力扣（LeetCode）

再来一道模拟单调栈的题目（其实早就写了但现在才做题解）。

当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

当前高度小于等于栈顶高度，入栈。

当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈。

while(!st.isEmpty() && height[st.peek()] < height[i]){
    int cur = st.pop();
    if(st.isEmpty()){
        break;
    }
    int l = st.peek();
    int r = i;
    int h = Math.min(height[r],height[l]) - height[cur];
    ans += (r - l - 1) * h;
}

AC代码如下：

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        //创建一个栈
        Stack<Integer> st = new Stack<>();
        for(int i = 0;i < height.length;++i){
            while(!st.isEmpty() && height[st.peek()] < height[i]){
                //cur表示水洼的底部
                int cur = st.pop();
                if(st.isEmpty()){
                    break;
                }
                //获取水池的左右两端的墙的下标。
                int l = st.peek();
                int r = i;
                int h = Math.min(height[r],height[l]) - height[cur];
                ans += (r - l - 1) * h;
            }
            st.push(i);
        }
        return ans;
    }
}