42. Trapping Rain Water

Thinking:

• Method:DP

class Solution {
    public int trap(int[] height) { //DP
        if(height == null || height.length == 0) return 0;
        int len = height.length;
        int[] left = new int[len];
        int leftMax = height[0];
        int[] right = new int[len];
        int rightMax = height[len - 1];
        for(int i = 1; i < len; i++){
            if(height[i] > leftMax){
                leftMax = height[i];
                continue;
            }
            left[i] = leftMax - height[i];
        }
        for(int i = len - 2; i >= 0; i--){
            if(height[i] > rightMax){
                rightMax = height[i];
                continue;
            }
            right[i] = rightMax - height[i];
        }
        int count = 0;
        for(int i = 0; i < len; i++){
            count += Math.min(left[i], right[i]);
        }
        return count;
    }
}

• Method 2:
  1. 先想清楚一个问题，我们一定会找到一个全局最高点，在最高点左侧，最高值是递增的，在最高点右侧最高值是递减的。
  • [0,1,0,2,1,0,1,3,2,1,2,1]， 3是最高点。
    1. 想清楚条件一以后，每个位置能装水量由左侧的最高值决定（因为有右侧的最高值保证了一定能包含左侧最高值。）右侧同理。

class Solution {
    public int trap(int[] height) { //DP
        if(height == null || height.length == 0) return 0;
        int len = height.length;
        int leftMax = 0;
        int rightMax = 0;
        int left = 0; int right = len - 1;
        int count = 0;
        while(left < right){
            if(height[left] <= height[right]){
                if(height[left] > leftMax){
                    leftMax = height[left];
                    left++;
                    continue;
                }
                count += leftMax - height[left] ;
                left++;
            }else{
                if(height[right] > rightMax){
                    rightMax = height[right];
                    right--;
                    continue;
                }
                count += rightMax - height[right];
                right--;
            }
        }
        return count;
    }
}

二刷

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;
        int len = height.length;
        int maxLeft = height[0];
        int[] lefts = new int[len];
        int maxRight = height[len - 1];
        int[] rights = new int[len];
        for(int i = 1; i < len; i++){
            if(height[i] > maxLeft){
                maxLeft = height[i];
                continue;
            }
            lefts[i] = maxLeft - height[i];
        }
        for(int i = len - 2; i >= 0; i--){
            if(height[i] > maxRight){
                maxRight = height[i];
                continue;
            }
            rights[i] = maxRight - height[i];
        }
        int result = 0;
        for(int i = 0; i < len; i++)
            result += Math.min(lefts[i], rights[i]);
        return result;
    }
}

Amazon session

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