【每日一题】直方图的水量

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

暴力破解：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
	//从1遍历到n-1的位置是因为左右均无护栏，不能存水！
        for (int i = 1; i < n - 1; i++) {
            int cur = height[i];

            //获取当前位置的左边最大值
            int l = Integer.MIN_VALUE;
            for (int j = i - 1; j >= 0; j--) l = Math.max(l, height[j]);
            if (l <= cur) continue;

            //获取当前位置的右边边最大值
            int r = Integer.MIN_VALUE;
            for (int j = i + 1; j < n; j++) r = Math.max(r, height[j]);
            if (r <= cur) continue;

            //计算当前位置可接的雨水，左右最大值间最小值减当前高度为当前位置可装的水量
            ans += Math.min(l, r) - cur;
        }
        return ans;
    }
}