【每日算法Day 86】接雨水

LeetCode 42. 接雨水 (opens new window)

题目描述

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

上面是由数组 [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

解题思路

拿到问题后我们如果想一步得到一个整体的答案是很困难的，而是应该着眼于局部，考虑每个柱子位置能接多少雨水，显然是该柱子左侧和右侧两个柱子高度的最大值中的最小值，那么对于每一个柱子，如果我们使用暴力搜索其左右的最大值，时间复杂度将达到O(n^2)。可以尝试使用两个数组来存储左右的最大值，这样能把时间复杂度降至O(n)。

public int trap(int[] height) {
    if (height == null || height.length < 3) return 0;

    int n = height.length;
    int[] leftMax = new int[n], rightMax = new int[n];
    leftMax[0] = height[0];
    rightMax[n - 1] = height[n - 1];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

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

还可使用双指针法，进一步将空间复杂度降到O(1)。在前面，我们通过数组能准确直到height[i]这根柱子左侧和右侧的最大值；而使用双指针法，我们可以直到height[left]左侧的最大值leftMax和height[right]右侧的最大值rightMax。如果leftMax < rightMax，虽然我们不能肯定rightMax是height[left]右侧的最大值，但我们知道了其右侧有比左侧最大值还要大的值。这就足够了因为height[left]处能接的雨水这时只与leftMax有关，计算完结果后移动左指针。如果leftMax > rightMax那么同理，如果二者相等，那么移动任意指针都是可以的。

public int trap(int[] height) {
    if (height == null || height.length < 3) return 0;
    int n = height.length, total = 0;
    int left = 0, right = n - 1, leftMax = 0, rightMax = 0;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        if (leftMax < rightMax)
            total += leftMax - height[left++];
        else
            total += rightMax - height[right--];
    }
    return total;
}