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

503.下一个更大元素II

代码随想录链接

题目

LeetCode-503.下一个更大元素II

给定一个循环数组, 在循环的情况下寻找每一个元素右侧的第一个比其大的元素.

题目分析

可以看作是单调栈连续对一个数组执行了两次, 且之间执行是连续的.

可以在for循环的控制条件里, 将i结束的条件设置为小于两倍的数组长度, 并在for循环内使用\(i\ \% \ nums.size()\) 来进行迭代.

题解

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

42.接雨水

代码随想录链接

题目

LeetCode-42.接雨水

给定一系列在横轴上摆放的柱子的高度, 求这些柱子和横轴之间所形成的容器最多能接多少雨水.

LeetCode-42.接雨水

如图, 黑色是柱子, 蓝色是雨水, 题目要求的就是蓝色块的面积(二维下可不是面积🐴)

题目分析

双指针法

针对每一个柱子上的面积进行单独考虑, 一个柱子上的蓝色块的面积, 由左右方向各自最高的共两根柱子中, 较矮的那根柱子和自身的高度差决定.

LeetCode-42.接雨水

例如, 柱子高度height[0,1,0,2,1,0,1,3,2,1,2,1] 对应的图片是上面这张图片, 当i = 2时, height[2] = 0, 其上方的积水为1个单位, 由左边高度为1的柱子和自身为0的柱子求得; i = 6时, height[6] = 1, 其上方积水为1个单位, 由左侧最高的柱子的高度2和自身高度1求得.

我们可以在针对每个柱子进行积水计算时, 分别找左侧最高的柱子和右侧最高的柱子, 但这样会有很多重复的计算, 解决办法之一是先将每个柱子的左侧最高高度和右侧最高高度进行一次计算并保存下来, 这样能降低时间复杂度.

单调栈

单调栈方法下, 一行一行地计算积水的量.

在给定柱子高度的环境下, 积水只会出现在有凹槽的地方, 有凹槽的地方一定是出现在从前向后遍历时, 由递减变为递增的状态处, 此时就应该进行横向的积水量计算.

LeetCode-42.接雨水(单调栈)

由前向后使用单调栈进行遍历时, 有三种情况:

• 栈顶索引对应的元素大于遍历到的元素

  此时将元素入栈符合栈顶到栈底元素递增的情况, 对应在柱子中, 是凹槽的左侧高度下降部分.

• 栈顶索引对应的元素等于遍历到的元素

  元素可以直接入栈, 并不影响计算, 或者只保存一者, 最终不影响结果.

• 栈顶索引对应的元素小于遍历到的元素

  此时说明凹槽出现了, 应该开始计算当前开始变高的柱子和左侧柱子形成的凹槽的单位.

题解

双指针法:

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2)
            return 0;
        vector<int> maxLeft(height.size(), 0);
        vector<int> maxRight(height.size(), 0);

        maxLeft[0] = height[0];
        for (int i = 1; i < height.size(); i++)
            maxLeft[i] = max(maxLeft[i - 1], height[i]);
        
        maxRight[height.size() - 1] = height.back();
        for (int i = height.size() - 2; i >= 0; i--)
            maxRight[i] = max(maxRight[i + 1], height[i]);

        int sum = 0;
        for (int i = 0; i < height.size(); i++) {
            int count = min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
};

单调栈:

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2)
            return 0;
        stack<int> st;
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] <= height[st.top()])
                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[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1;
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};