August 06, 2019

42. Trapping Rain Water

法1. 暴力法

Two Pointers - 对于每个index，找左右两侧最大值，相对小的一个减去当前高度为当前蓄水面积。 Time = O(n^2), Space = O(1)

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int l = i;
            int r = i;
            int lmax = height[i];
            int rmax = height[i];
            while (l >= 0) {
                if (height[l] > height[i]) {
                    lmax = Math.max(height[l], lmax);
                }
                l--;
            }
            while (r < height.length) {
                if (height[r] > height[i]) {
                    rmax = Math.max(height[r], rmax);
                }
                r++;
            }
            if (lmax != height[i] && rmax != height[i]) {
                res += Math.min(lmax, rmax) - height[i];
            }
        }
        return res;
    }
}

另一种做法，记录左右两边的高度。Time = O(n), Space = O(n)

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] leftMaxHeight = new int[height.length];
        int[] rightMaxHeight = new int[height.length];
        leftMaxHeight[0] = 0;
        for (int i = 1; i < height.length; i++) {
            leftMaxHeight[i] = Math.max(leftMaxHeight[i - 1], height[i - 1]);
        }
        rightMaxHeight[height.length - 1] = 0;
        for (int i = height.length - 2; i >= 0; i--) {
            rightMaxHeight[i] = Math.max(rightMaxHeight[i + 1], height[i + 1]);
        }
        int maxWater = 0;
        for (int i = 0; i < height.length; i++) {
            int curWater = Math.min(leftMaxHeight[i], rightMaxHeight[i]) - height[i];
            if (curWater < 0) {
                curWater = 0;
            }
            maxWater += curWater;
        }
        return maxWater;
    }
}

法2. Two Pointers (Optimized Solution)

Time = O(n), Space = O(1) 类似于贪心法的解法，两个指针相向而行。

参考讲解视频，讲的特别清楚。水位是由左右指针的短板决定的。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int res = 0;
        int leftmax = 0;
        int rightmax = 0;
        int i = 0;
        int j = height.length - 1;
        while (i < j) {
            leftmax = Math.max(leftmax, height[i]);
            rightmax = Math.max(rightmax, height[j]);
            if (leftmax < rightmax) {
                res += leftmax - height[i];
                i++;
            } else {
                res += rightmax - height[j];
                j--;
            }
        }
        return res;
    }
}

法3. 单调栈

decreasing stack - 存 index