代码随想Day59 | 503.下一个更大元素II、42. 接雨水

这道题和?739.?每日温度?几乎如出一辙，这道题的环形数组需要用下标取模，来模拟环形数组，其他的和每日温度相同，详细代码如下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //成环的问题用取模来解决
        vector<int>res(nums.size(),-1);
        stack<int>s;
        s.push(0);
        for(int i=1;i<nums.size()*2;i++)
        {
            while(!s.empty()&&nums[i%nums.size()]>nums[s.top()])
            {
                res[s.top()]=nums[i%nums.size()];
                s.pop();
            }
            s.push(i%nums.size());
        }
        return res;

    }
};

42.?接雨水??

接雨水这道题目是?面试中特别高频的一道题，也是单调栈?应用的题目

这道题的思路主要就是需要确定当前元素的左边更大的元素和右遍更大的元素，思路整体和之前的相似，但是在当前元素大于栈口元素的处理逻辑，需要注意左边的比其更大的元素就是栈口的下一个元素，其次就是确定长宽，具体思路在：

42.?接雨水??

详细代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        if(height.size()==0) return res;
        stack<int>s;
        s.push(0);
        for(int i=1;i<height.size();i++)
        {
            while(!s.empty()&&height[i]>height[s.top()])
            {
                int mid = height[s.top()];
                s.pop();
                if(!s.empty()) //以防异常
                {
                    int h = min(height[i],height[s.top()])-mid;
                    int w = i-s.top()-1;
                    res+=h*w;
                }
            }
            s.push(i);
        }
        return res;
        

    }
};