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

503.下一个更大元素II

https://leetcode.cn/problems/next-greater-element-ii/

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

42. 接雨水

https://leetcode.cn/problems/trapping-rain-water/

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0;
        vector<int> leftHeight(height.size(), 0);
        vector<int> rightHeight(height.size(), 0);
        leftHeight[0] = height[0];
        for (int i = 1; i < height.size(); i++) {
            leftHeight[i] = max(leftHeight[i - 1], height[i]);
        }
        rightHeight[height.size() - 1] = height[height.size() - 1];
        for (int i = height.size() - 2; i >= 0; i--) {
            rightHeight[i] = max(rightHeight[i + 1], height[i]);
        }
        int result = 0;
        for (int i = 0; i < height.size(); i++) {
            result += min(leftHeight[i], rightHeight[i]) - 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++) {
            while (!stk.empty() && height[stk.top()] < height[i]) {
                int low = height[stk.top()];
                stk.pop();
                if (!stk.empty()) {
                    int high = min(height[stk.top()], height[i]);
                    int wide = i - stk.top() - 1;
                    result += wide * (high - low);
                }
            }
            stk.push(i);
        }
        return result;
    }
};