42. 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 can trap after raining.

Solution

双指针，设置当前左侧的最大高度left和右侧的最大高度right。

分别从两侧遍历height[]数组，当出现更高的height时更新left和right。
否则记录left和right与height[i]的差值，并记录在数组waterLeft[]和waterRight[]中。

遍历两个数组，添加两者中的最小值到volume。

*由于单个参数只记录了一侧的最大值，因此最大值另一侧的水的体积会被多计算，因此分别从两侧遍历来获得最小值。

Code

class Solution {
    public int trap(int[] height) {
        int n = height.length, left = 0, right = 0, volume = 0;
        int[] waterLeft = new int[n], waterRight = new int[n];
        
        for(int i = 0; i < n; i++){
            if(left <= height[i]) left = height[i];
            else waterLeft[i] = left - height[i];
        }
        
        for(int i = n - 1; i >= 0; i--){
            if(right <= height[i]) right = height[i];
            else waterRight[i] = right - height[i];
        }
        
        for(int i = 0; i < n; i++){
            volume += Math.min(waterLeft[i], waterRight[i]);
        }
        
        return volume;
    }
}