LeetCode 42.接雨水

直觉来看，每一个正方形可以容纳1个单位的水。
按列来求，迭代求每一列可以容纳多少单位的水，累加。
找出每一列左右两边最高的柱子，遍历时，不用关注第一列和最后一列。然后找到两边最高中较小的柱子，与当前列高度比较，大于，则可以装水，其他不可以。
代码：

class Solution {
    public int trap(int[] height) {
        // 宽都是1，柱子。h为height[i]。容量是由每个柱子的高度差产生的
        // 遍历每一列，分别求出两边最高的墙
        int sum = 0;
        // 两端不用考虑
        for (int i = 1; i < height.length-1; i++) {
            int max_left = 0;
            // 找出左边最高 ，从右到左找
            for (int j = i-1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }

            int  max_right = 0;
            // 找出右边最高, 从左到右找，注意这里的x < height.length, 要到最后一个柱子
            for (int x = i +1; x < height.length; x++) {
                if (height[x] > max_right) {
                    max_right = height[x];
                }
            }
            // 找出较小的
            int min = Math.min(max_left, max_right);
            // 只有较小的一段大于当前列才会有水，否则不会有
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }

        }
        return sum;

    }
}