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!
思路：动态规划。第一次存储从开始到i最高的位置，求最高位置a之前的存水量=a与a之前最高位置b之间的水量+b与b之前最高位置c之间的水量...
第二次存储从末尾到i最高的位置，求最高位置a之后的存水量=a与a之前最高位置m之间的水量+m与m之前最高位置n之间的水量...
class Solution { public: int trap(int A[], int n) { if(n<=2) return 0; int ret = 0; int start; int end; int* highestTillNow = new int[n]; //状态 highestTillNow[0] = 0; for(int i = 1; i<n;i++) //第一次扫描，从头向后 { if(A[i] > A[highestTillNow[i-1]]) { highestTillNow[i] = i; } else highestTillNow[i] = highestTillNow[i-1]; } end = highestTillNow[n-1]; //最高位置 //求最高位置前的储水量 while(end>1) { start = highestTillNow[end-1]; //最高位置前的次高位置 if(A[start]==0) break; for(int i = start+1; i <= end-1; i++) { ret += A[start]-A[i]; } end = start; } //reverse end = highestTillNow[n-1]; highestTillNow[n-1] = n-1; for(int i = n-2; i>end; i--) //第二次扫描，从尾向前 { if(A[i] > A[highestTillNow[i+1]]) { highestTillNow[i] = i; } else highestTillNow[i] = highestTillNow[i+1]; } while(end < n-2) { start = highestTillNow[end+1]; if(A[start]==0) break; for(int i = start-1; i >= end+1; i--) { ret += A[start]-A[i]; } end = start; } return ret; } };
42. Trapping Rain Water (Array; DP)
原文：http://www.cnblogs.com/qionglouyuyu/p/4863574.html