0042-接雨水

题目链接

点击查看【music163】

题目描述

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

示例

示例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 个单位的雨水（蓝色部分表示雨水）。

提示

• n == height.length
• 0 <= n <= 3 * 10

• 0 <= height[i] <= 10

  思路

  思路1：动态规划

  借用官方题解的图解释：
  
  通过dp求出leftMax和rightMax，然后从0开始求每一个柱子所在位置能接的雨水。

  思路2：单调栈

  维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组height中的元素递减。
  如果只有两个柱子，则无法存水，此时直接返回0；当栈中有至少2个元素时，设栈顶元素为top，它下面的一个元素为left，则有height[left]>=height[top]；
  同时，设当前的下标为i：

• 若height[i]>height[top]，则i与left之间就可以形成一个容器，容器底为i-left-1，高度为min(height[left],height[i])-height[top]。

• 若height[i]<=height[top]，则将i入栈。

  思路3：双指针

  在思路1动态规划中我们使用了两个数组，导致空间复杂度为。但我们还能将其降到。
  注意到思路1中两个数组分别从左到右和从右到左计算的，因此考虑双指针。我们设两个指针为left和right，在遍历的过程中，设遍历过的最大高度分别为leftMax和rightMax，则指针处接水量由两个高度中的最小值决定。
  指针移动的策略为：移动最大高度较小的一边。因为如果移动高的一遍不会改变容量。由此策略我们可以得出如下结论：

  当height[left]>height[right]时，leftMax>rightMax；当height[left]<=height[right]时，leftMax<=rightMax。

题解

思路1：动态规划

class Solution {
   public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < height.size(); ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }
        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i > -1; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

思路2：单调栈

class Solution {
   public:
    int trap(vector<int>& height) {
        stack<int> st;
        int ans = 0;
        for (int i = 0; i < height.size(); ++i) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int topIndex = st.top();
                st.pop();
                if (st.empty()) {
                    break;
                }
                int distance = i - st.top() - 1;
                ans += (min(height[i], height[st.top()]) - height[topIndex]) * distance;
            }
            st.push(i);
        }
        return ans;
    }
};

思路3：双指针

class Solution {
   public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] <= height[right]) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
};

复杂度分析

思路1：动态规划

• 时间复杂度：

• 空间复杂度：

  思路2：单调栈

• 时间复杂度：，从0到n-1的每个下标最多只会入栈和出栈各一次。

• 空间复杂度：

  思路3：双指针

• 时间复杂度：

• 空间复杂度：