[LeetCode] Trapping Rain Water

週六下午看到這題，覺得蠻有趣的。

而且”看起來”是個不難的hard，之前跟同學討論過有些easy反而天殺的很難

周末想說應該是個stack的題目，找到凹谷之後開始pop掉，直到遇到另一個山頭。

就像array[3]~array[7] 依序放入stack

(2)=>(2,1)=>(2,1,0)=>(2,1,0),1

這時候發現有凹谷了，基底是0、兩個高度一樣為1、長度為1 => ans +=1*(1-0)，然後pop掉

(2,1)=>(2,1) , 3

這次又有凹谷，基底為1、兩邊高度取min為2，長度為3 => ans += 3 * (2-1)

接著因為3比較高，當成right side新的山頭，把stack清空再放入3

想過幾個case好像可以做做看，但寫了之後覺得variables也太多了吧，這不是leetcode的style

腦羞看了discuss看到標題o(1) space，我的方法就算是對的應該也是廢到炸掉QQ

看了一下別人的solution，分別從左右兩側找當前左右兩側最高的山頭，然後從比較低的那一側灌水(想像這個容器只要考慮一邊就好)

如果下一格沒有比目前山頭更高，就計算這格跟目前計算左側或右側最高的山頭的高低差是多少，累積起來就是答案，如果發現有更高的山頭就取代掉(此時這側已經形成一個完整container惹)，然後換邊計算。

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

我的腦袋是不是真的退化惹惹惹惹，但至少還看得懂code就是了XD

明天是周二，該洗洗睡了。