週六下午看到這題,覺得蠻有趣的。
而且”看起來”是個不難的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
明天是周二,該洗洗睡了。