代码随想录算法训练营第五十九天 | 503. 下一个更大元素 II、42. 接雨水

503. 下一个更大元素 II

题目链接：503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

思路与实现

我的想法是，用单调栈遍历两遍数组nums，第一遍遍历的结果保留，第二遍遍历在原来的基础上继续。代码写完通过，如下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> stk;
        vector<int> results(nums.size(), -1);
        for(int i = 0;i<2 * nums.size();i++){
            int curi = i % nums.size();
            while(!stk.empty() && nums[stk.top()] < nums[curi]){
                results[stk.top()] = nums[curi];
                stk.pop();
            }
            stk.push(curi);
        }
        return results;
    }
};

42. 接雨水

题目链接：42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路与实现

用两个单调栈来处理这个问题。首先从左向右遍历，记录下每个柱子左边的最长的柱子的长度。再从右向左遍历，记录下每个柱子右边的最长的柱子的长度。当前柱子能够接的雨水等于左右最长柱子的最小值，减去当前柱子的长度。代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk1, stk2;
        vector<int> leftMax(height.size(), -1);
        vector<int> rightMax(height.size(), -1);

        for(int i = 0;i<height.size();i++){
            if(stk1.empty()) stk1.push(i);
            else{
                if(height[stk1.top()] > height[i]){
                    leftMax[i] = height[stk1.top()];
                }
                else stk1.push(i);
            }
        }

        for(int i = height.size() - 1;i >= 0;i--){
            if(stk2.empty()) stk2.push(i);
            else{
                if(height[stk2.top()] > height[i]){
                    rightMax[i] = height[stk2.top()];
                }
                else stk2.push(i);
            }
        }

        int result = 0;
        for(int i = 0;i<height.size();i++){
            if(leftMax[i] != -1 && rightMax[i] != -1){
                int minAround = min(leftMax[i], rightMax[i]);
                result += (minAround - height[i]);
            }
        }
        return result;
    }
};

看了一下，我这种其实是双指针写法。单调栈的思路，参考代码随想录，代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;
        stack<int> stk;
        stk.push(0);
        int result = 0;
        for(int i = 1;i<height.size();i++){
            if(height[i] < height[stk.top()]){
                stk.push(i);
            }
            else if(height[i] == height[stk.top()]){
                stk.pop();
                stk.push(i);
            }
            else{
                while(!stk.empty() && height[i] > height[stk.top()]){
                    int mid = stk.top();
                    stk.pop();
                    if(!stk.empty()){
                        int h = min(height[stk.top()], height[i]) - height[mid];
                        int w = i - stk.top() - 1;
                        result += h * w;
                    }
                }
                stk.push(i);
            }
        }
        return result;
    }
};

上面的代码简化版：

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