Trapping Rain Water

Question

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Solution

這題也是難在數學，或者是說，難在想到該怎麼解這道問題，程式部分非常少。九章教的思路是，觀察這樣一個 array，我們會發現能夠 trap 的水的最小值，其實是取決於最左跟最右的兩根柱子內比較小的那根。因此，我們想到或許可以用兩個指針，start, end 來處理。處理過程中，我們先動比較小的那根，因為同理，小的那根能夠決定可以 trap 多少水。當我們遇到比當前這根還矮的柱子時，我們就計算之間的差，然後 update 當前這根變成最矮的那根，因為我們把它填上來了

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

        int water = 0;
        int start = 0, end = height.length - 1;
        while (end > start) {
            if (height[end] > height[start]) {
                if (height[start + 1] < height[start]) {
                    water += height[start] - height[start + 1];
                    height[start + 1] = height[start];
                }
                start++;
            } else {
                if (height[end - 1] < height[end]) {
                    water += height[end] - height[end - 1];
                    height[end - 1] = height[end];
                }
                end--;
            }
        }
        return water;
    }