题目

有一个array，size为n，储存的值皆>=0，值代表那格的海拔高度，这样会形成很多凹槽，如果下雨了，会积多少雨水呢?

以下图为例子，答案是6

解法

用2个pointer，i与j ，i先固定，j往後，当j的海拔高大於或等於i的海拔高，代表有可能有凹槽，另外一个情况是走到最後了，都是i大於j，但也要处理一次。
e.g.

接着就先算出最高是多少，所以i与j取小的，然後用一个pointer反走回去直到i，然後计算会积多少水。
这里不能直接用i往前走到j，从上面的例子，应该看的出来会发生什麽事。

Code

class Solution {
public:
    int trap(vector<int>& height) {
        int trap_water = 0;
        int i = 0;
        int j = 1;
        while(j < height.size()){
             if (height[i] <= height[j] || j == height.size() - 1) {
                int level = min(height[i], height[j]);
                int k = j - 1;
                while (k != i) {
                    level = max(height[k], level);
                    trap_water += level - height[k--];
                }
                i = j;
            }
            
            j++;
        }
        return trap_water;
    }
};