trapping-rain-water

problem

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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

1 2	Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

var trap = function(height) {
    if(height.length < 3) {
        return 0;
    }
    let sum = 0;
    let i = 0;
    let j = height.length - 1;
    let leftMax = height[i];
    let rightMax = height[j];
    while (i <= j) {
        leftMax = Math.max(leftMax, height[i]);
        rightMax = Math.max(rightMax, height[j]);
        if (leftMax >= rightMax) {
            sum += (rightMax - height[j]);
            j--;
        } else if(leftMax <= rightMax){
            sum += (leftMax - height[i]);
            i++;
        }

    }
    return sum;
};

// Input: [0,1,0,2,1,0,1,3,2,1,2,1]
// Output: 6

// Input: [0,0,1,0,0]
// Output: 0

// time O(n) space O(1)

method

这道题的思路是对每个位置，计算当前位置的min(rightMax, rightMax),然后减去当前位置的高度，在逐个相加
i的位置从左到右，j的位置从右到左
leftMax是nodecrease的，rightMax是noincrease的，所以，
leftMax >= rightMax, 那么rightMax所处的位置j就能确定当前min(rightMax, rightMax) 为rightMax，
leftMax < rightMax, 那么leftMax所处的位置i就能确定当前min(rightMax, rightMax) 为leftMax，