leetcode: 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.

 

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!

原问题链接：https://leetcode.com/problems/trapping-rain-water/

 

问题分析

    我们先来看一个最简单的示例，看能否找到思路。在前面问题的要求中，要能够实现有水的存储，那么它最简单的形式也应该是一个凹型的。所以说，对于这个数组来说它至少要有３个元素。也就是说它的长度至少应该为３，否则没法构成这么一个可以储水的结构。

　　所以说，一个最简单的储水结构应该如下图：

　　针对这种最简单的形式，我们需要有一个左边和一个右边。然后在上图中红线下所覆盖的地方即为它所储水的部分。在这种情况下，很明显，我们应该取两个边中间比较矮的那个。在实际要求中则是要去其中较小的那个值。

　　有了上述这个最简单的示例，我们知道一点。如果我们要找里面可以储水的地方，需要首先从两边开始取长度短的一方，然后向长的一方移动来计算。一直到碰到一个比当前的那个长度长的边。在实际的情况中，在向长的边移动的时候，不是所有的边的高度都是０，更可能出现一些如下的情况：

 　　实际上这种情况也比较简单。如上图中用红线所标注的样式。每次我们可以用当前的那个矮的一边的高度减去当前的值就可以得到一个针对当前单元的储水情况。然后将这些值都加起来。

　　所以按照前面的讨论我们就已经得到一个基本的思路了。就是一开始我们首先取数组两头的元素。然后判断小的那个元素作为移动的起始点。向大的元素那边移动。我们以这个小元素的值作为当前的minHeight值。循环向大的元素方向比较移动，碰到比minHeight小的当前元素，则将minHeight - 当前元素的值作为当前储水的一部分累加到一个表示所有储水量的变量中。假设这个变量定义为water。如果碰到比当前minHeight大的元素，则停止向原来方向的移动。我们继续比较两边当前的边的长度，再来选择出一个minHeight作为下一轮移动的标杆。 

 　　所以按照这个思路，我们在具体的实现的代码中应该定义两个索引，一个left，一个right。left = 0, right = height.length - 1。最外层的循环是while(left < right)，保证一直比较到最终两个索引点相遇。假设最开始是左边的索引点小，那么就有

 

while(left < right && height[left] <= minHeight) {
    water += minHeight - height[left];
    left++;
}

 　同理，如果是右边的索引点小，那么它向大的元素那边移动的代码如下：

 

while(left < right && height[right] <= minHeight) {
    water += minHeight - height[right];
    right--;
}

     在这两个循环跳出来之后，说明我们已经碰到比minHeight大的点了。所以需要再次求minHeight的值。它的求法还是一样，取left, right两个位置中小的那个。

 

　　综合上述的讨论，我们可以得到如下的详细实现代码：

 

public class Solution {
    public int trap(int[] height) {
        if(height == null || height.length < 3) return 0;
        int n = height.length, l = 0, r = n - 1, water = 0, minHeight = 0;
        while (l < r) {
            while (l < r && height[l] <= minHeight)
                water += minHeight - height[l++];
            while (r > l && height[r] <= minHeight)
                water += minHeight - height[r--];
            minHeight = Math.min(height[l], height[r]);
        }
        return water;
    }
}