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.

描述

给定 n 个非负整数，求图中蓝色部分

分析

每个值，其实都是由其左右的最高点 maxleft，maxright 所决定的，即 min(maxleft , maxright) - height[i]

代码

public class Solution {
    public int trap(int[] height) {
        
        int len = height.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int maxleft = -1, maxright = -1;

        for (int i = 0; i < len; i++) {
            if (maxleft < height[i]) {
                maxleft = height[i];
            }
            left[i] = maxleft;
        }

        for (int i = len - 1; i >= 0; i--) {
            if (maxright < height[i]) {
                maxright = height[i];
            }
            right[i] = maxright;
        }

        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += (Math.min(left[i], right[i]) - height[i]);
        }
        
        return sum;
    }
}