代码随想录训练营第五十九天503.下一个更大元素II42. 接雨水

两道题都是对于单调栈存储序号的延申应用。

503.下一个更大元素II

题目链接?503. 下一个更大元素 II - 力扣（LeetCode）

讲解链接?代码随想录 (programmercarl.com)

?相比于温度变化，本题增加了条件。数组是循环的，也就是数组末尾元素的下一位是开头元素（nums.size()->0),此时可以结合温度记录单调栈算法，对于每一个元素：

1、小于栈顶元素的塞入

2、等于栈顶元素的塞入

3、大于栈顶元素的比较，并赋值

同时循环数组两次，也就是说在循环完毕之后再循环一次，在代码中实现的就是把i换成i%nums.size(),循环条件改为，i<nums.size()*2:

        for(int i=1;i<nums.size()*2;i++){
            
            if(nums[i%nums.size()]<=nums[st.top()]){
                st.push(i%nums.size());
            }
            else{
                while(!st.empty()&&nums[i%nums.size()]>nums[st.top()]){
                    result[st.top()]=nums[i%nums.size()];
                    st.pop();
                }
                st.push(i%nums.size());
            }
        }

42. 接雨水

题目链接?42. 接雨水 - 力扣（LeetCode）

讲解链接?代码随想录 (programmercarl.com)

?同样使用单调栈思想进行解释，在循环过程中，对于遇到的元素有如下三种处理方法：

1、当前高度小于栈顶下标对应的高度，将该元素塞入栈中；

2、当前高度等于栈顶下标对应的高度，将栈顶元素弹出，塞入新的位置下标，计算面积时同时将两个相等元素的顶上积水空间计算出来；

3、当前高度大于栈顶下标对应的高度，记录栈顶下标，在while循环中以此计算栈中第二第三元素与当前元素所围成面积的值（直到当前元素不再大于依次被弹出后的栈的顶端元素）每一次计算一个空间层数：

        for(int i=1;i<height.size();i++){
            if(height[i]<height[st.top()]){
                st.push(i);
            }
            else if(height[i]==height[st.top()]){
                st.pop();
                st.push(i);
            }
            else{
                while(!st.empty()&&height[i]>height[st.top()]){
                    int mid=st.top();
                    st.pop();
                    if(!st.empty()){
                        int h=min(height[i],height[st.top()])-height[mid];
                        int w=i-st.top()-1;
                        sum+=h*w;
                    }
                }
                st.push(i);
            }

        }

此外，应用单调栈解决问题一定要注意，栈中记录的是数组元素的下标递增排序。