/*
https://leetcode.com/problems/trapping-rain-water/
Runtime: 1 ms, faster than 98.11% of Java online submissions for Trapping Rain Water.
Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Trapping Rain Water.
*/
class Solution {
    public int trap(int[] height) {
        int waters = 0, l = 0, r = height.length - 1;
        while (l < r) {
            int lh = height[l], rh = height[r];
            if (lh < rh) {
                while(++l < r && lh >= height[l]) {
                    waters += lh - height[l];
                }
            } else {
                while(l < --r && rh >= height[r]) {
                    waters += rh - height[r];
                }
            }
        }
        return waters;
    }
}