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

题目介绍

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

简单分析

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

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

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

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;
}

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

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

代码

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;