[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惹)，然後換邊計算。

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

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