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.
只要找到最高的那个柱子，然后从两边往最高的那个柱子移动。
能存储多少水是由短的那个柱子决定的。
在i这个位置，如果我们知道i之前最高的柱子j，那么i这个位置能存的水就是height[j]-heigt[i]
class Solution { public: int trap(vector<int>& height) { int size = height.size(); if(size<=1){ return 0; } int maxHeight = height[0]; int maxHeightIndex = 0; for(int i=1;i<size;i++){ if(height[i]>maxHeight){ maxHeight = height[i]; maxHeightIndex = i; } } int res = 0; int curMaxHeight = height[0]; for(int i=1;i<maxHeightIndex;i++){ if(height[i]<curMaxHeight){ res += curMaxHeight-height[i]; }else{ curMaxHeight = height[i]; } } curMaxHeight = height[size-1]; for(int i=size-2;i>maxHeightIndex;i--){ if(height[i]<curMaxHeight){ res += curMaxHeight-height[i]; }else{ curMaxHeight = height[i]; } } return res; } };
原文：http://www.cnblogs.com/zengzy/p/5005300.html