LeetCode 42. 接雨水

暴力解法

对于数组中的每个元素，下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。

class Solution {
    public int trap(int[] height) {
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int maxLeft = 0, maxRight = 0;
            for (int j = i; j >= 0; j--) {  // 往左寻找左边最大高度
                maxLeft = Math.max(maxLeft, height[j]);
            }
            for (int j = i; j < height.length; j++) {    // 往右寻找右边最大高度
                maxRight = Math.max(maxRight, height[j]);
            }
            res += Math.min(maxLeft, maxRight) - height[i];     // 当前位置的雨水：两边最大高度的较小值减去当前高度的值
        }
        return res;
    }
}

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

动态解法

在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。我们可以存储寻找过的最大值。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        int res = 0;
        int size = height.length;
        int[] maxLeft = new int[size];      // 保存左边最大值
        int[] maxRight = new int[size];     // 保存右边最大值
        maxLeft[0] = height[0];
        for (int i = 1; i < size; i++) {
            maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);   // i处的左边最大值在i-1处最大值与height[i]中产生
        }
        maxRight[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            maxRight[i] = Math.max(height[i], maxRight[i + 1]);     // i处的右边最大值在i+1处最大值与height[i]中产生
        }
        for (int i = 1; i < size - 1; i++) {
            res += Math.min(maxLeft[i], maxRight[i]) - height[i];
        }
        return res;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

双指针

• 当从左向右处理 left 指针时，左边的最大值 leftMax 对它而言是可信的，但 rightMax 是不可信的，rightMax 未必是 left 指针右边的最大值。
• 当从右向左处理 right 指针时，同理，右边的最大值 rightMax 对它而言是可信的，但 leftMax 是不可信的。
• 对于 left 指针，它的左边的最大值一定为 leftMax , 它的右边的最大值大于等于 rightMax 。
• 当 leftMax < rightMax 时，我们可以去处理 left 指针，通过 leftMax 就可以计算出当前存多少水，无论 rightMax 多大都不会影响结果，计算完 left 向右移动一位。
• 反之，我们处理 right 指针，通过 rightMax 计算当前存多少水，然后 right 向左移动一位。

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)