42. 接雨水

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

503. 下一个更大元素 II

两个数组拼成一个

class Solution {
public:
    // 如何处理循环?   两个数组拼成一个
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        if (n == 0) return res;
        stack<int> sta;
        for (int i = 0; i < n * 2; i ++)
        {
            while (!sta.empty() && nums[i % n] > nums[sta.top()])
            {
                res[sta.top()] = nums[i % nums.size()];
                sta.pop();
            }
            sta.push(i % nums.size());
        }
        return res;
    }
};