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

目录

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

思路

代码

题目链接：42. 接雨水

思路

代码

总结

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

思路

        找右边比自己大的元素，只不过是在循环数组中，只需要遍历数组两遍，数组下标取余即可

代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        vector<int> result(len, -1);
        if (len == 1)
            return result;
        stack<int> st;
        st.push(0);
        // 遍历两遍数组
        for (int i = 1; i < 2 * len; i++) {
            // 下标都用模取
            if (nums[i % len] <= nums[st.top()]) {
                st.push(i % len);
            } else {
                while (!st.empty() && nums[i % len] > nums[st.top()]) {
                    result[st.top()] = nums[i % len];
                    st.pop();
                }
                st.push(i % len);
            }
        }
        return result;
    }
};

题目链接：42. 接雨水

思路

        按列计算，每列宽度为1，重点是计算高度：

        高度 = min(左边最高的柱子，右边最高的柱子) - 当前柱子的高度

        暴力解法，每次分别向左右遍历寻找左右最高的柱子，最后选择二者较小的值，时间复杂度O(n^2)，空间复杂度O(1)

        双指针法，其实就是先计算每个位置的左边和右边的最大高度，时间复杂度0(n)，空间复杂度O(n)

        单调栈法，按行计算雨水。单调栈从栈头到栈底应该是从小到大的顺序，栈头是当前柱子的刚度，栈头的下一个是左边的柱子，新加入的应该是右边的柱子，而栈头则是凹槽。遇到相同高度的柱子是，更新下标为新柱子的下标，因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。栈中保存下标，用以计算宽度，高度则通过下标索引数组中的高度。遍历柱子高度时有三种情况：

        ①当前高度 < 栈顶下标对应的元素，将当前下标push进栈内，保持单调递增

        ②当前高度 = 栈顶下标对应的元素，将栈顶元素弹出，将当前下标push进站内，因为按行计算雨水，宽度要根据右边更新

        ③当前高度 > 栈顶下标对应的元素，记录栈顶元素为mid，然后弹出，此时栈顶下标对应高度为左边柱子高度height[st.top()]，遍历的当前元素为右边柱子高度height[i]，而mid对应高度为凹槽，那么此时就可以累加雨水了。

        高度 h = min(height[st.top()], height[i]) - height[mid]

        宽度 w = i - st.top() - 1

        雨水 = h * w

代码

双指针

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

        // 计算左边最高高度
        Lmaxheight[0] = height[0];
        for (int i = 1; i < len; i++) {
            Lmaxheight[i] = max(Lmaxheight[i - 1], height[i]);
        }

        // 计算右边最高高度
        Rmaxheight[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            Rmaxheight[i] = max(Rmaxheight[i + 1], height[i]);
        }

        // 计算雨水
        int result = 0;
        for (int i = 0; i < len; i++) {
            result += min(Rmaxheight[i], Lmaxheight[i]) - height[i];
        }
        return result;
    }
};

单调栈

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0; // 记录雨水
        int len = height.size();
        if (len <= 2)
            return sum; // 至少三个元素才能收集到雨水
        stack<int> st;
        st.push(0);

        for (int i = 1; i < len; i++) {
            if (height[i] < height[st.top()]) {
                st.push(i);
            } else if (height[i] == height[st.top()]) {
                st.pop();
                st.push(i);
            } else {
                while (!st.empty() && height[i] > height[st.top()]) {
                    int mid = st.top(); // 记录凹槽
                    st.pop(); // 弹出后，当前top就是左边柱子高度的下标
                    // 弹出后栈可能为空
                    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;
    }
};

总结

        ①循环数组的处理方法，复制数组得到一个二倍长度的数组；遍历两遍数组，用取余的方式遍历

        ②42.接雨水的解决方法很巧妙，不过在处理过程中还是要遵循同一个规则，要么按行计算，要么按列计算

        ③暴力解法在每一步都需要重新寻找左右柱子的最大高度，时间复杂度O(n^2)

        ④双指针法将计算左右柱子最大高度的步骤放在计算雨水之外，时间复杂度O(n)，不过还是要遍历三次数组，还增加了额外的空间

        ⑤单调栈法是按行计算，通过高度与宽度的乘积得到雨水总量。因为雨水的收集需要一个凹槽，也就是说先单调递减，后单调递增。由于使用栈的原因，那么栈头到栈底就是单调递增，当遇到比栈头大的元素时，说明右边柱子比当柱子高，出现凹槽，可以收集雨水