大人物都是从小人物时不断地尝试而造就。

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解题代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int h = 0;
        int sum = 0;
        int max_height = 0;
        int hole = 0;
        int wall = 0;
        for(int i = 0;i < height.size();i++){
            max_height = max(max_height,height[i]);
        }
        while(max_height > h){
            int left = 0;
            int right = 0;
            for(int i = 0;i < height.size();i++){
                if(height[i] > h){
                    left = i;
                    break;
                }
            }
            for(int i = height.size() - 1;i >= 0;i--){
                if(height[i] > h){
                    right = i;
                    break;
                }
            }
            wall = min(height[left],height[right]);

            for(int i = left + 1;i < right;i++){
                if(height[i] < wall){
                    if(height[i] > h){
                        sum += wall - height[i];
                    }else 
                        sum += wall - h;
                    
                }
            }
            h = wall;
        }
        return sum;
    }
};

解读与收获：

我本人的想法是，首先对整个数组进行一次遍历，找到数组中的最大值作为循环的限制条件。设置变量h为当前层数，然后进入while循环，在while循环中首先从左到右遍历，找到第一个值大于h的下标，记为left，同理从右到左遍历，记为right。接下来在left和right中的较小者（记为wall）围成的区域中进行操作，遍历此区域，从中减去无法存储雨水的区域，这里分两种情况，如果值大于h，则wall与当前height[i]的差值就是储水区域，如果值小于h，则wall和h的差值是储水区域，第二种这样处理的原因是防止已经计算过的区域重复计算，遍历完当前层后，更新h的值为当前wall的高度。

但这样时间复杂度十分滴高，大概率因为进行了太多次的循环，下面是官方题解代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

另外我单独写了一份可以可视化样例的程序，能方便调试吧。

(比较丑)

#include<head.h>
using namespace std;

int main(int argc, char const *argv[])
{
    vector<int> n = {5,5,1,7,1,1,5,2,7,6};
    int max = 7;
    while(max > 0){
        for(int i = 0; i < n.size(); i++){
            if(n[i] >= max){
                cout<<0;
            }else 
                cout<<" ";
        }
        cout<<endl;
        max--;
    }
    getchar();
    return 0;
}