題目

有一個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;
    }
};