1.题目

接雨水题解

这题真他妈经典，老子搞了半小时才彻底搞懂。记录一下思路，免得下次又忘。

核心思路

每个位置能接的雨水量 = min(左边最高的柱子, 右边最高的柱子) - 当前柱子高度

简单来说就是：

找当前柱子左边最高的（不包括自己）
找当前柱子右边最高的（不包括自己）
取这俩的较小值
如果这个值比当前柱子高，差值就是能接的雨水

具体实现

第一步：预处理左右最大值

先搞两个数组：

leftMax[i]：表示第i个柱子左边最高的柱子高度（不包含自己）
rightMax[i]：表示第i个柱子右边最高的柱子高度（不包含自己）

计算leftMax：

从左往右扫
维护一个当前最大值max
对于每个位置i，leftMax[i] = max（记录之前遇到的最大值）
然后更新max = Math.max(max, height[i])

1
2
3
4
5


int max = 0;
for (int i = 0; i < n; i++) {
    leftMax[i] = max;
    max = Math.max(max, height[i]);
}

计算rightMax：

从右往左扫
同样维护一个当前最大值max
对于每个位置i，rightMax[i] = max
然后更新max = Math.max(max, height[i])

1
2
3
4
5


max = 0;
for (int i = n - 1; i >= 0; i--) {
    rightMax[i] = max;
    max = Math.max(max, height[i]);
}

第二步：计算雨水

现在有了leftMax和rightMax，对于每个位置：

取leftMax[i]和rightMax[i]的较小值
如果这个值 > height[i]，说明能接雨水
雨水 = 较小值 - height[i]

1
2
3
4
5
6


for (int i = 0; i < n; i++) {
    int min = Math.min(leftMax[i], rightMax[i]);
    if (min > height[i]) {
        ans += (min - height[i]);
    }
}

例子分析

以[0,1,0,2,1,0,1,3,2,1,2,1]为例：

计算leftMax：
- 从左往右，记录遇到的最大值
- 得到：[0,0,1,1,2,2,2,2,3,3,3,3]
计算rightMax：
- 从右往左，记录遇到的最大值
- 得到：[3,3,3,3,3,3,3,2,2,2,1,0]
计算雨水：
- 比如i=2，height=0
- leftMax=1, rightMax=3
- min=1
- 1 > 0，所以接1单位水

复杂度

时间：O(n)，扫了3遍数组
空间：O(n)，用了两个辅助数组

优化思路

其实可以用双指针把空间降到O(1)，不过这个解法已经够直观了，下次再研究优化的。

代码总结

 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


public int trap(int[] height) {
    int n = height.length;
    int ans = 0;
    
    // 左边最大值
    int[] leftMax = new int[n];
    int max = 0;
    for (int i = 0; i < n; i++) {
        leftMax[i] = max;
        max = Math.max(max, height[i]);
    }
    
    // 右边最大值
    int[] rightMax = new int[n];
    max = 0;
    for (int i = n - 1; i >= 0; i--) {
        rightMax[i] = max;
        max = Math.max(max, height[i]);
    }
    
    // 计算雨水
    for (int i = 0; i < n; i++) {
        int min = Math.min(leftMax[i], rightMax[i]);
        if (min > height[i]) {
            ans += (min - height[i]);
        }
    }
    
    return ans;
}

这题真他妈经典，记住这个思路就完事了！

LeetCode42.接雨水