Trapping Rain Water _Water

行是知之始,知是行之成。这篇文章主要讲述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.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6
【Trapping Rain Water】

文章图片

分析
对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是 min(max_left,
max_right) - height。所以
1. 从左往右扫描一遍，对于每个柱子，求取左边最大值；
2. 从右往左扫描一遍，对于每个柱子，求最大右值；
3. 再扫描一遍，把每个柱子的面积并累加。
也可以，
1. 扫描一遍，找到最高的柱子，这个柱子将数组分为两半；
2. 处理左边一半；
3. 处理右边一半。
代码

1 package StacksAndqueues; 2 3 public class TrappingRainWater { 4 5public static void main(String[] args) { 6// TODO Auto-generated method stub 7//从左往右找到最大，再从右到左找到最大，目前最大-目前array[i]; 找到其中最小的，即为存水量。 8int[] array= {0,1,0,2,1,0,1,3,2,1,2,1}; 9System.out.println(trap(array)); 10} 11 12public static int trap(int[] array) { 13if (array.length == 0) 14return 0; 15int len = array.length - 1; 16int[] maxl = new int[len + 1]; 17int[] maxr = new int[len + 1]; 18int cap = 0, total = 0; 19for (int i = len; i > = 0; i--) { 20maxr[i] = cap; 21if (array[i] > cap) 22cap = array[i]; 23} 24cap = 0; 25for (int i = 0; i < = len; i++) { 26maxl[i] = cap; 27if (array[i] > cap) 28cap = array[i]; 29} 30for (int i = 0; i < = len; i++) { 31int c = Math.min(maxl[i], maxr[i]) - array[i]; 32if (c > 0) 33total += c; 34} 35return total; 36} 37 }