蓄水问题

输入：一个序列
输出：总共蓄水量
用例：[0,1,0,2,1,0,1,3,2,1,2,1] ===> 6

蓄水量示意图

分析

这个东西跟之前做过的一个蓄水问题很像。之前好像只是让求最大蓄水量。这个题目让求总共的。

思路

求每个位置的蓄水量，遍历加和。
Brute Force.
每个位置左右求蓄水边界。从而求出该位置的蓄水量

代码

package day_10;

// 求总的蓄水量问题
// Brute Force  求出每个位置的蓄水量最后加和。
public class TrappingRainWater {
    public int trap(int[] height){
        int sum = 0;
        for(int i=1;i<height.length-1;i++){
            int left = 0;
            int right = 0;
            int res = 0;
            for(int j=i;j>=0;j--){
                left = height[j]>=left ? height[j]:left;
            }
            for(int j=i;j<height.length;j++){
                right = height[j]>=right ? height[j]:right;
            }
            res = left<=right?left:right;
            res = res-height[i];
            System.out.println(res);
            sum = sum+res;
        }
        return sum;
    }

    public static void main(String[] args){
        int[] a={0,1,0,2,1,0,1,3,2,1,2,1} ;
        TrappingRainWater t = new TrappingRainWater();
        System.out.println(t.trap(a));
    }
}

说实话是比较蠢的解法。还没看牛逼的解法。