lc-42

//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. 
//
// 
// Example 1: 
//
// 
//Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
//Output: 6
//Explanation: The above elevation map (black section) 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.
// 
//
// Example 2: 
//
// 
//Input: height = [4,2,0,3,2,5]
//Output: 9
// 
//
// 
// Constraints: 
//
// 
// n == height.length 
// 1 <= n <= 2 * 104 
// 0 <= height[i] <= 105 
// 
// Related Topics Array Two Pointers Dynamic Programming Stack Monotonic Stack 
// 👍 19838 👎 279


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];

        for (int i = 1; i < height.length; i++) {
            if (height[i - 1] > leftMax[i - 1]) {
                leftMax[i] = height[i - 1];
            } else {
                leftMax[i] = leftMax[i - 1];
            }
        }

        for (int i = height.length - 2; i >= 0; i--) {
            if (height[i + 1] > rightMax[i + 1]) {
                rightMax[i] = height[i + 1];
            } else {
                rightMax[i] = rightMax[i + 1];
            }
        }

        int result = 0;

        for (int i = 0; i < height.length; i++) {
            int lower = Math.min(leftMax[i], rightMax[i]);

            if (height[i] < lower) {
                result += (lower - height[i]);
            }
        }

        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)