leetcode 链接：接雨水

题目

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

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

输入：height = [4,2,0,3,2,5]
输出：9

解答 & 代码

解法一：

时间复杂度 O(N)，空间复杂度 O(1)

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2)    // 特殊情况：如果柱子数 < 3, 就没法接水
            return 0;

        int totalCap = 0;        // 总容水量
        int left = 0;            // 当前容器的左边界

        // 找到第一个非零的柱子作为第一个容器的左边界
        while(left < height.size() && height[left] == 0)    
            ++left;

        // 寻找每个容器的左、右边界，并分别计算各容器的容量
        while(left < height.size() - 1)        // 注意：left < height.size() - 1 就停止，因为如果 left 是最后一根柱子，那么右边也没法接水了
        {
            int right = left + 1;        // 当前容器的右边界
            int maxRightIdx = right;    // 当前容器左边界往右最高的柱子下标

            // 寻找高度 >= 左边界的柱子作为当前容器的右边界
            while(right < height.size() && height[right] < height[left])
            {
                if(height[right] >= height[maxRightIdx])
                    maxRightIdx = right;
                ++right;
            }

            // 如果左边界右侧没找到比左边界高的柱子，
            // 那么将左边界右侧最高（如果有相同高度的取最右侧的）的柱子作为当前容器的右边界
            if(right >= height.size())
                right = maxRightIdx;

            // 计算当前容器的容量
            int minHeight = height[right] > height[left] ? height[left] : height[right];    // 左右边界中较低的高度
            int cap = (right - left - 1) * minHeight;
            for(int i = left + 1; i < right; ++i)
                cap -= height[i];

            // 当前容器的容量如果 > 0，则加入到总容量
            if(cap > 0)
                totalCap += cap;

            // 将当前容器的右边界作为下个容器的左边界
            left = right;
        }
        return totalCap;
    }
};

执行结果：

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 17.14% 的用户
内存消耗：13.8 MB, 在所有 C++ 提交中击败了 66.12% 的用户

解法二：动态规划

时间复杂度 O(N)，空间复杂度 O(N)

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        if(size < 3)        // 特殊情况：如果柱子数 < 3, 就没法接水
            return 0;

        vector<int> leftMax(size);    // 存储每个位置左边柱子最大高度（含该位置自身）
        vector<int> rightMax(size);    // 存储每个位置右边柱子最大高度（含该位置自身）

        // 动态规划计算 leftMax 数组
        leftMax[0] = height[0];
        for(int i = 1; i < size; ++i)
            leftMax[i] = height[i] > leftMax[i - 1] ? height[i] : leftMax[i - 1];

        // 动态规划计算 rightMax 数组
        rightMax[size - 1] = height[size - 1];
        for(int i = size - 2; i >= 0; --i)
            rightMax[i] = height[i] > rightMax[i + 1] ? height[i] : rightMax[i + 1];

        int cap = 0;    // 总容量
        // 计算每个位置的容量 = 最右两边柱子最大高度的较小值 - 该位置柱子高度
        for(int i = 0; i < size; ++i)
        {
            int minHeight = leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i];
            cap += minHeight - height[i];    // 加到总容量
        }

        return cap;
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 68.99% 的用户
内存消耗：14 MB, 在所有 C++ 提交中击败了 49.23% 的用户

解法三：单调栈

单调栈结构：★★☆☆单调栈结构，★★☆☆单调栈结构(进阶

时间复杂度 O(N)，空间复杂度 O(N)

class Solution {
public:
    int trap(vector<int>& height) {
        int cap = 0;        // 总容量
        stack<int> idxS;    // 单调栈，存储数组下标，从栈底到栈顶的下标对应的高度递减

        for(int i = 0; i < height.size(); ++i)    // 遍历数组，当前遍历到下标 i
        {
            while(!idxS.empty() && height[i] > height[idxS.top()])
            {
                int top = idxS.top();
                idxS.pop();
                if(!idxS.empty())
                {
                    int left = idxS.top();
                    int w = (i - left -1);
                    int minHeight = height[i] < height[left] ? height[i] : height[left];
                    int h = minHeight - height[top];
                    cap += w * h;
                }
            }
            idxS.push(i);
        }
        return cap;
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 68.99% 的用户
内存消耗：14.1 MB, 在所有 C++ 提交中击败了 25.33% 的用户

解法四：双指针

在解法二（动态规划）的基础上进行优化，使得时间复杂度为 O(N)，空间复杂度为 O(1)

class Solution {
public:
    int trap(vector<int>& height) {
        int cap = 0;    // 总容量

        int left = 0;                    // 左指针（下标）
        int right = height.size() - 1;    // 右指针（下标）
        int leftMax = 0;                // 当前左指针左边最大高度（含当前左指针本身高度）
        int rightMax = 0;                // 当前右指针右边最大高度（含当前右指针本身高度）

        // 遍历，左指针往右遍历，右指针往左遍历，直到相遇
        while(left < right)
        {
            // 更新左、右最大高度
            leftMax = height[left] > leftMax ? height[left] : leftMax;
            rightMax = height[right] > rightMax ? height[right] : rightMax;

            // 如果左边高度更小，那么计算左指针指向位置的容量
            if(leftMax < rightMax)
            {
                // 木桶原理，左边高度更小，就说明最大能装水的高度就是左边最大高度
                cap += leftMax - height[left];
                ++left;        // 左指针右移
            }
            // 如果右边高度更小，那么计算右指针指向位置的容量
            else
            {
                cap += rightMax - height[right];
                --right;    // 右指针左移
            }
        }

        return cap;
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 68.99% 的用户
内存消耗：13.8 MB, 在所有 C++ 提交中击败了 80.83% 的用户