Leetcode 42*. 接雨水

发表于

题目

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

img

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例：

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路

对我来说，果然还是很困难啊。。。因为一开始做就已经没有思路了，但是其实再多思考思考，还是可以想出暴力解法的。当然，暴力解法感觉也很难想到。

暴力解法

直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。

算法

  • 初始化 ans=0
  • 从左向右扫描数组：
    • 初始化 max_left=0和max_right=0
    • 从当前元素向左扫描并更新：
      • max_left = max(max_left, height[j])
    • 从当前元素向右扫描并更新：
      • max_right = max(max_right, height[j])
    • 将min(max_left, max_right)-height[i]累加到ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int trap(vector<int>& height){
    int len = height.size();
    int ans = 0;
    for (int i = 1; i < len - 1; i++){
        int leftMax = 0, rightMax = 0;
        for (int j = i; j >= 0; j--){
            leftMax = max(leftMax, height[j]);
        }
        for (int j = i; j < len; j++){
            rightMax = max(rightMax, height[j]);
        }
        ans += min(leftMax, rightMax) - height[i];
    }
    return ans;
}

当时，上面的方法其实每次都要重复计算最大值。其实我们可以实现将左右两侧的最大值存储起来。再计算，这样的时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int trap(vector<int>& height){
    int len = height.size();
    if (len == 0) return 0;
    int ans = 0;
    vector<int> leftMax(len), rightMax(len);
    leftMax[0] = height[0];
    for (int i = 1; i < len; i++){
        leftMax[i] = max(leftMax[i - 1], height[i]);
    }
    rightMax[len - 1] = height[len - 1];
    for (int i = len - 2; i >= 0; i--){
        rightMax[i] = max(rightMax[i + 1], height[i]);
    }
    for (int i = 1; i < len - 1; i++){
        ans += min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
}