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.
翻译：
给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。
例如，
给出 [0,1,0,2,1,0,1,3,2,1,2,1], 返回6
如下图：
我的思路是这样的：先设上面的数组为A，先找出整个数组中的最大值，上面的例子中是第八个数，也就是A[7]，大小为3。然后以这个值为基准，计算这个值左边的雨水存量，可以找出这个值左边的最大值为A[3]，大小为2。这个时候你可以知道，A[3]到A[7]之间的存水量为A[4]到A[7]之间的空间，减去实心部分：（7 - 3 - 1）* A[3] - A[4] - A[5] - A[6] = 4。然后在以A[3]为基准，求左边的存水量，就是一个递归。可以得出左边的存水量为5。同样的道理：右边存水量为1。最后的存水量为5 + 1 = 6。
写代码的时候为了方便思考，我把求左边的存水来那个和
class Solution { public: int trap(vector<int>& height) { int len = height.size(); int max = 0; int maxindex = -1; int water = 0; int begin = 0; int end = len - 1; for (int i = 0; i < len; i++) {//获取数组的最高值 if (max < height[i]) { max = height[i]; maxindex = i; } } water = water + leftpartialwater(height, begin, maxindex, max);//计算最高值左边的雨水量 water = water + rightpartialwater(height, maxindex, end, max);//计算最高值右边的雨水量 return water; } int leftpartialwater(vector<int> &heights, int begin, int end, int max) {//计算左边的存水量 int curwater = 0; if (begin >= end) { curwater = 0; } else { int curmax = 0; int curmaxindex = -1; for (int i = begin; i < end; i++) {//查找最大值左边的其他元素的最大值 if (curmax <= heights[i]) { curmax = heights[i]; curmaxindex = i; } } curwater = (end - curmaxindex - 1) * curmax; int other = 0; for (int j = curmaxindex + 1; j < end; j++) { other = other + heights[j]; } curwater = curwater - other;//计算之前的最大值到当前求出的最大值之间的存水量 curwater = curwater + leftpartialwater(heights, begin, curmaxindex, curmax);//递归，求当前的最大值到下一个最大值之间的存水量 } return curwater; } int rightpartialwater(vector<int> &heights, int begin, int end, int max) {//计算右边的存水量 int curwater = 0; if (begin >= end) { curwater = 0; } else { int curmax = 0; int curmaxindex = - 1; for (int i = begin + 1; i <= end; i++) {//查找最大值右边的其他元素的最大值 if (curmax <= heights[i]) { curmax = heights[i]; curmaxindex = i; } } curwater = (curmaxindex- begin - 1) * curmax; int other = 0; for (int j = begin + 1; j < curmaxindex; j++) { other = other + heights[j]; } curwater = curwater - other;//计算之前的最大值到当前求出的最大值之间的存水量 curwater = curwater + rightpartialwater(heights, curmaxindex, end, curmax);//递归，求当前的最大值到下一个最大值之间的存水量 } return curwater; } };要是大家还有什么高见，请指教啊。
