心之所向便是光

Leetcode 42.接雨水

  • 2021-06-08
  • 作者 Ender
  • 2.84K 字
  • 次阅读

题目描述：

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

示例 1：

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

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

提示：

1
2
3
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

链接：

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

题目分析

  这道题有点像 Leetcode 11.盛最多水的容器，因此也是考虑用双指针的做法。与那道题不同的是，这里的每个柱子并不是没有厚度的“壁”，而且对于所有的“坑”都会盛上水，而不是只选取其中两个壁之间盛水。但是思路应该是一致的，我们可以从两边往中间搜索。这是因为观察可以发现，每个较低的柱子，只要两边有高于它的柱子，则可以填上水直到和较低的一边柱子平齐。而我们在利用双指针搜索的时候，优先扩展较低的那边，则可以保证未搜索的区域不会影响已搜索区域填水的高度。
  具体的算法是，维护两个变量记录左边已搜索区域的最大高度 maxleft 和右边已搜索区域的最大高度 maxright，而 left 和 right 分别记录当前搜索的左右指针（下标）。如果当前是左边的最大高度 maxleft 较小，则扩展左边，若出现了更高的柱子则更新 maxleft，较低的柱子则填上雨水直到和 maxleft 平齐，也即更新 water 值；同样的，如果是 maxright 较小，则扩展右边，相应地更新 maxright 或者 water 值。最后两个指针相遇的时候搜索结束，得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0) return 0;

        int water = 0;
        int maxleft = 0, maxright = 0;
        int left = 0, right = height.size()-1;

        while(left <= right){
            if(maxleft <= maxright){
                if(height[left] > maxleft){
                    maxleft = height[left];
                }
                else{
                    water += maxleft - height[left];
                }
                left++;
            }
            else{
                if(height[right] > maxright){
                    maxright = height[right];
                }
                else{
                    water += maxright - height[right];
                }
                right--;
            }
        }
        return water;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组大小。两个指针从左右两端开始遍历直到相遇，总共只对数组进行了一层遍历。
  空间复杂度：$O(1)$。我们只需要常数个变量进行记录。

官方题解

  下面的代码是官方题解中双指针的代码，减少了一次判断，将更新 max 值和 water 值（这里是变量 ans)整合到了一起。相应的指针相遇条件有所不同（因为我们上面的代码更新完 max 值也对指针进行了移动，因此指向的永远是未搜索的区域，必须两个指针已经重合后错开才算搜索完毕）。
  官方题解中还有动态规划和栈等其他解法，也可以提供一定的解决思路，时间复杂度都是一样的 $O(n)$，但是动态规划和栈解法均需要 $O(n)$ 的空间。感兴趣的可以阅读 接雨水 - 力扣官方题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 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;
    }
};
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-22