Trapping Rain Water

题目
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.

答案
maintain i左边最高的bar x，i右边最高的bar y
i位置上有多少水取决于x和y短的那一节
用x或y减去当前i的bar，就知道i能有多少水

class Solution {
    // e.g input: 2 0 2
    public int trap(int[] height) {
        int left = 0, right = height.length - 1, n = height.length;
        int[] leftmax = new int[n], rightmax = new int[n];
        int area = 0;

        // Generate leftmax (leftmax[0] = 0)
        for(int i = 1; i < n; i++) {
            leftmax[i] = Math.max(leftmax[i - 1], height[i - 1]);
        }

        // Generate rightmax
        for(int i = n - 2; i >= 0; i--) {
            rightmax[i] = Math.max(rightmax[i + 1], height[i + 1]);
        }

        // left max:  0 2 2
        // right max: 2 2 0
        for(int i = 0; i < n; i++) {
            int water_level = Math.min(leftmax[i], rightmax[i]);
            if(height[i] >= water_level) continue;
            else area += (water_level - height[i]);
        }

        return area;
    }
}