Noob
0%

Trapping Rain Water

发表于 更新于 分类于 ，

Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

DP

记录当前Bar左边和右边的最大高度，取两个最大高度的最小值min，当前Bar对总结果的贡献为min-当前Bar的高度，将每个Bar对结果的贡献累加起来即可。该算法时间复杂度2N，空间复杂度O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int trap(int[] height) {
    if(height == null || height.length == 0) return 0;
    int sum = 0, rightMax = 0;
    int[] right = new int[height.length];
    for(int i = height.length - 1; i >= 0; --i) {
        right[i] = rightMax;
        rightMax = Math.max(rightMax, height[i]);
    }
    int leftMax = 0;
    for(int i = 0; i < height.length; ++i) {
        int water = Math.min(right[i], leftMax) - height[i];
        if(water > 0)
            sum += water;
        leftMax = Math.max(leftMax, height[i]);
    }
    return sum;
}

Two Pointers

使用两个指针l和r，初始时l指向第一个Bar，r指向最后一个Bar。然后每次从l和r指向的Bar选出高度最小的。如果l-Bar较小，那么统计l-Bar右面比l-Bar高度小的Bar与l-Bar的差值，直到右面的高度值超过l-Bar。r-Bar类似向左统计。两个指针相遇结果就统计完成。该算法时间复杂度N，空间复杂度O（1）。另一个巧妙使用多指针思想的题目：http://jeffzzf.github.io/2015/07/01/Sort-colors/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int trap(int[] height) {
    if(height == null || height.length == 0) return 0;
    int l = 0, r = height.length - 1, sum = 0;
    while(l < r) {
        int min = Math.min(height[l], height[r]);
        if(min == height[l]) {
            while(l < r && min > height[++l])
                sum += min - height[l];
        } else {
            while(l < r && min > height[--r])
                sum += min - height[r];
        }
    }
    return sum;
}

类似于Trapping rain water，不过不是找出最大的容器而是计算所有边容纳的水量。采用类似的思路，维护首尾两个指针以及从两端开始的最大高度，每次从容器高度小得一端收缩，计算与维护的最大高度相比的差值，累加后的值即为总的水量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) {
    if(height == null || height.length <= 1) return 0;
    int n = height.length;
    int maxLeft = 0, maxRight = 0;
    int left = 0, right = n - 1;
    int result = 0;
    while(left < right) {
        if(height[left] < height[right]) {
            maxLeft = Math.max(maxLeft, height[left]);
            result += maxLeft - height[left];
            ++left;
        } else {
            maxRight = Math.max(maxRight, height[right]);
            result += maxRight - height[right];
            --right;
        }
    }
    return result;
}