Trapping Rain Water leetcode

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.

题目：给一个凹凸不平的积木组合，问能盛住的水的体积为多少？

思路：每一点能接住的水量取决于它左边的最高高度，和右边的最高高度中相对低的那个。

water[i] = min(leftHighest[i], rightHighest[i]) - A[i];

如果左右两边的最高高度都比它低，water[i] < 0，说明没法接住水。

leftHighest[]和rightHighest[]可以通过两遍扫描，用O(n)的时间求出来。or:DP

代码：

class Solution {
public:int trap(int A[], int n) {if(A == NULL || n<=0)return 0;int* leftMax = new int[n];int* rightMax = new int[n];int max = A[0];leftMax[0] = A[0];for(int i=1;i<n;i++) {if(max<A[i-1])max = A[i-1];leftMax[i] = max;}max = A[n-1];rightMax[n-1] = A[n-1];for(int i = n-2;i>=0;i--) {if(max < A[i+1])max = A[i+1];rightMax[i] = max;}int sum = 0;for(int i=0;i<n;i++) {int h = leftMax[i]<rightMax[i]? leftMax[i]:rightMax[i];int vom = h-A[i];if(vom>0)sum += vom;}return sum;}
};