蓄水问题
输入:一个序列
输出:总共蓄水量
用例:[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));
}
}
说实话是比较蠢的解法。还没看牛逼的解法。