lintcode：接雨水

接雨水

给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。

如上图所示，海拔分别为 [0,1,0,2,1,0,1,3,2,1,2,1], 返回 6.

解题

先遍历一遍找到最高点，然后分别从两边开始，往最高点所在位置遍历，水位只会增高不会减小，且一直和最近遇到的最大高度持平，这样知道了实时水位，就可以边遍历边计算面积。

左到最高点，海拔高度下降的时候计算水位，左边最近比他高的海拔减去自己的海拔，这是该海拔的水位量。当遇到更高的海拔的时候更新海拔高度。

右到最高点，海拔高度下降的时候计算水位, 右边最近比他高的海拔减去自己的海拔，这是该海拔的水位量。当遇到更高的海拔的时候更新海拔高度。

 1 public class Solution {
 2     /**
 3      * @param heights: an array of integers
 4      * @return: a integer
 5      */
 6     public int trapRainWater(int[] A) {
 7         // write your code here
 8         int n = A.length;
 9         if(n <= 2) return 0;
10         int max = -1, maxInd = 0;
11         int i = 0;
12         for(; i < n; ++i){
13             if(A[i] > max){
14                 max = A[i];
15                 maxInd = i;
16             }
17         }
18         int area = 0, root = A[0];
19         for(i = 0; i < maxInd; ++i){
20             if(root < A[i]) root = A[i];
21             else area += (root - A[i]);
22         }
23         for(i = n-1, root = A[n-1]; i > maxInd; --i){
24             if(root < A[i]) root = A[i];
25             else area += (root - A[i]);
26         }
27         return area;
28     }
29 }

Java Code

class Solution:
    # @param heights: a list of integers
    # @return: a integer
    def trapRainWater(self, A):
        # write your code here
        n = len(A)
        if(n <= 2):
            return 0
        max = -1
        maxInd = 0
        for i in range(n):
            if A[i]> max:
                max = A[i]
                maxInd = i
        leftMax = A[0]
        area = 0 
        for i in range(maxInd):
            if leftMax < A[i]:
                leftMax = A[i]
            else:
                area = area + leftMax - A[i]

        rightMax = A[n-1]
        for i in range(n-1,maxInd,-1):
            if rightMax< A[i]:
                rightMax = A[i]
            else:
                area = area + rightMax - A[i]
      
        return area

Python Code