Leetcode#42 Trapping Rain Water

浏览数：29 / 时间：2015年06月11日

原题地址

不妨手动模拟一下，观察是否有规律可寻。

假设从位置0开始，我们有一个矩形条

技术分享

向右扩展，我们遇到了第二个矩形条，假设这个矩形条比第一个矮：

技术分享

我们继续向右扩展，直到遇到比第一个矩形条高（或者相等）的矩形条：

技术分享

那么显然，蓝色的部分就是装水的部分，把这部分累加到最终的结果中

技术分享

然后，以新发现的这个矩形条为左边界，继续向右扩展...

技术分享

通过模拟我们发现，先固定一个左边界，然后不断向右寻找右边界，哪个是右边界呢？第一个比左边界高（或者相等）的矩形条就是右边界。

这样做显然会有个问题，比如下面这种情况，最右边的矩形条是最后一个矩形条，此时蓝色的部分就不会被算进去，因为最右边的矩形条比红色箭头所指的矩形条矮，它不是右边界。

技术分享

怎么办呢？倒过来（从右向左）用同样的方式扫一遍就行了。

但是这样还有一个问题，看下面的情况。当左右边界（红色箭头所指）等高时，这部分装水的容量一共会被计算两次（从左向右扫一次，从右向左扫一次）。

技术分享

解决方法也很简单，只要规定，从左向右扫的时候左边界一定小于右边界，从右向左扫的时候左边界一定大于等于右边界即可。

代码：

 1 int trap(int A[], int n) {
 2   int sum = 0;
 3   int acc = 0;
 4   int i = 0;
 5   int j = 0;
 6 
 7   // 从左向右扫
 8   i = 0;
 9   j = 1;
10   acc = 0;
11   while (i < n && j < n) {
12     if (A[j] < A[i])
13       acc += A[i] - A[j];
14     if (A[j] > A[i]) {
15       sum += acc;
16       acc = 0;
17       i = j;
18     }
19     j++;
20   }
21 
22   // 从右向左扫
23   i = n - 1;
24   j = n - 2;
25   acc = 0;
26   while (i >= 0 && j >= 0) {
27     if (A[j] < A[i])
28       acc += A[i] - A[j];
29     else {
30       sum += acc;
31       acc = 0;
32       i = j;
33     }
34     j--;
35   }
36 
37   return sum;
38 }