给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。
如上图所示，海拔分别为 [0,1,0,2,1,0,1,3,2,1,2,1], 返回 6.
解题
先遍历一遍找到最高点，然后分别从两边开始，往最高点所在位置遍历，水位只会增高不会减小，且一直和最近遇到的最大高度持平，这样知道了实时水位，就可以边遍历边计算面积。
左到最高点，海拔高度下降的时候计算水位，左边最近比他高的海拔 减去 自己的海拔 ，这是该海拔的水位量。当遇到更高的海拔的时候更新海拔高度。
右到最高点，海拔高度下降的时候计算水位, 右边最近比他高的海拔 减去 自己的海拔 ，这是该海拔的水位量。当遇到更高的海拔的时候更新海拔高度。
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] A) {
// write your code here
int n = A.length;
if(n <= 2) return 0;
int max = -1, maxInd = 0;
int i = 0;
for(; i < n; ++i){
if(A[i] > max){
max = A[i];
maxInd = i;
}
}
int area = 0, root = A[0];
for(i = 0; i < maxInd; ++i){
if(root < A[i]) root = A[i];
else area += (root - A[i]);
}
for(i = n-1, root = A[n-1]; i > maxInd; --i){
if(root < A[i]) root = A[i];
else area += (root - A[i]);
}
return area;
}
}
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