Leetcode 42 接雨水 (Trapping Rain Water) 题解分析

发表于 更新于 分类于 ， 阅读次数： 阅读次数： Disqus：

题目介绍

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

简单分析

其实最开始的想法是从左到右扫区间，就是示例中的第一个水槽跟第二个水槽都可以用这个办法解决

前面这种是属于右侧比左侧高的情况，对于左侧高右侧低的就不行了，（写这篇的时候想起来可以再反着扫一遍可能可以）

所以这个方案不好，贴一下这个方案的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int trap(int[] height) {
    int lastLeft = -1;
    int sum = 0;
    int tempSum = 0;
    boolean startFlag = true;
    for (int j : height) {
        if (startFlag && j <= 0) {
            startFlag = false;
            continue;
        }
        if (j >= lastLeft) {
            sum += tempSum;
            tempSum = 0;
            lastLeft = j;
        } else {
            tempSum += lastLeft - j;
        }
    }
    return sum;
}

后面结合网上的解法，其实可以反过来，对于每个格子找左右侧的最大值，取小的那个和当前格子的差值就是这一个的储水量了

理解了这种想法，代码其实就不难了

代码

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
int n = height.length;
if (n <= 2) {
    return 0;
}
// 思路转变下，其实可以对于每一格算储水量，算法就是找到这一格左边的最高点跟这一格右边的最高点，
// 比较两侧的最高点，取小的那个，然后再跟当前格子的高度对比，差值就是当前格的储水量
int maxL[] = new int[n];
int maxR[] = new int[n];
int max = height[0];
maxL[0] = 0;
// 计算左侧的最高点
for (int i = 1; i < n - 1; i++) {
    maxL[i] = max;
    if (max < height[i]) {
        max = height[i];
    }
}
max = height[n - 1];
maxR[n - 1] = 0;
int tempSum, sum = 0;
// 计算右侧的最高点，并且同步算出来储水量，节省一个循环
for (int i = n - 2; i > 0; i--) {
    maxR[i] = max;
    if (height[i] > max) {
        max = height[i];
    }
    tempSum = Math.min(maxL[i], maxR[i]) - height[i];
    if (tempSum > 0) {
        sum += tempSum;
    }
}
return sum;