首页 > 代码库 > Trapping Rain Water leetcode java
Trapping Rain Water leetcode java
题目：
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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
题解：
参考：低调小一（http://blog.csdn.net/wzy_1988/article/details/17752809）的解题思路
那么如何求A[i]的左右高度呢？ 要知道，能盛多少水主要看短板。那么对每个A[i]来说，要求一个最高的左短板，再求一个最高的右短板，这两个直接最短的板子减去A[i]原有的值就是能成多少水了。
所以需要两遍遍历，一个从左到右，找最高的左短板；一个从右到左，找最高的右短板。最后记录下盛水量的总值就是最终结果了。
代码如下：
2 if (A == null || A.length == 0)
3 return 0;
4
5 int i, max, total = 0;
6 int left[] = new int[A.length];
7 int right[] = new int[A.length];
8
9 // from left to right
10 left[0] = A[0];
11 max = A[0];
12 for (i = 1; i < A.length; i++) {
13 left[i] = Math.max(max, A[i]);
14 max = Math.max(max, A[i]);
15 }
16
17 // from right to left
18 right[A.length-1] = A[A.length-1];
19 max = A[A.length-1];
20 for (i = A.length-2; i >= 0; i--) {
21 right[i] = Math.max(max, A[i]);
22 max = Math.max(max, A[i]);
23 }
24
25 // trapped water (when i==0, it cannot trapped any water)
26 for (i = 1; i < A.length-1; i++) {
27 int bit = Math.min(left[i], right[i]) - A[i];
28 if (bit > 0)
29 total += bit;
30 }
31
32 return total;
33 }
对照着代码再看原来的例子：
index: 0 1 2 3 4 5 6 7 8 9 10 11
A[index]: 0 1 0 2 1 0 1 3 2 1 2 1
left[index]: 0 1 1 2 2 2 2 3 3 3 3 3
right[index]: 3 3 3 3 3 3 3 3 2 2 2 1
min[i]: 0 1 1 2 2 2 2 3 2 2 2 1
bit[i]: - 0 1 0 1 2 1 0 0 1 0 0
那么根据上表可以算出最终结果是6。
Reference：http://blog.csdn.net/wzy_1988/article/details/17752809