Trapping rain water (linear time, const space) - Teeeeeebag/LeetCode GitHub Wiki

1. using stack
2. use two pointers
   Keep track of leftMax and rightMax, if leftMax<rightMax, we can store leftMax-h[l] water for sure

public class Solution {
    public int trap(int[] height) {
        if (height.length < 3){
            return 0;
        }
        int water = 0, l = 0, r = height.length-1, leftMax = height[l], rightMax = height[r];
        while (l <= r){
            if (leftMax < rightMax){
                leftMax = Math.max(height[l], leftMax);
                water += leftMax - height[l];
                ++l;
            } else {
                rightMax = Math.max(height[r], rightMax);
                water += rightMax - height[r];
                --r;
            }
        }
        return water;
    }
}