Monotonic Stack – 陪你刷題

Monotonic stack 時間複雜度. 看到for 內又有while 迴圈，會覺得時間複雜度到O (n^2) ，但其實每個元素都只會被push 再被pop 一次，因此僅需O(n) 的 ... 跳至主要內容 Leetcode邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有bug一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。

這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

本篇要來探討的是MonotonicStack。

什麼是MonotonicStack Stack我們都了解，有著First-in-Last-out的特性，而MonotonicStack則是stack內的元素都保持著Monotonic(單調性)。

每次加新元素到stack時，stack內的元素都保持Monotonic(可以是單調遞增或是單調遞減)。

搭配Array使用，Array的每個元素必定會被放入stack中。

一旦出了stack，就不會再被放進去。

該如何理解MonotonicStack 想像Array的index代表每個人的座號，index內存放的是身高，我們可以透過monotonic來找每個人後方第一個比他高的人，如下圖: MonotonicStack內可以放身高，也可以放對應的座號。

MonotonicStack操作框架 要操作MonotonicStack，就必須謹記以下性質: MonotonicStack內的元素一定維持monotonic特性(單調遞增或單調遞減)。

每個元素都會加入stack，如果加入新元素會破壞monotonic，就必須將stack頂端元素移除，不斷移除stack頂端元素直到不違反monotonic，接著再加入元素。

MonotonicStack可以幫助找到向左/向右走訪第一個比當前元素小/大的元素，左/右跟小/大總共有四種組合。

如果要向左找第一個比input元素小的元素，以下圖為例， 從Array的起點開始走訪並依序加入stack，stack內元素都維持單調遞增的排序，直到準備放入7時，放入7會破壞單調遞增，因此必須pop元素直到可以維持單調遞增，當7可以放入stack之前，此時stacktop元素即是第一個比7小的元素。

Stack頂端的元素應該保持是向左找第一個比input小的元素，且top會是stack內最大的，(要找的是第一個比input元素小的，因此越小的應該越要在stack底部，才不會輕易被popout)，stack內的元素pop出來的結果就應該遞減。

如果是要向右找呢?很簡單，就從array尾端往前依序走訪處理即可，向右找第一個比input元素大的，stacktop元素會是stack內最小的，MonotonicStack內的元素pop出來就必須維持遞增。

MonotonicStack框架程式碼 下面展示的例子是尋找每個input元素其右手邊第一個比他大的元素。

由於是找右手邊的元素，所以從Array尾端往前依序處理。

vectornextGreaterElement(vector*nums) { vectorans(nums.size()); stackst; //從矩陣尾端往前走訪 for(inti=nums.size()-1;i>=0;i--) { /** *要維持stack內都是比新元素還要大且越接近stack底端元素 *越大，堆疊頂端元素就不能小於要push進堆疊的元素， *如果小於就移除頂端元素。

*/ while(!st.empty()&&nums[i]>=st.top()) { st.pop() } //當stack內為空，代表找不到比他大的 //若stack不為空，stack頂端元素就是 //第一個比他大的元素 ans[i]=st.empty()?-1:st.top(); //每個元素一定會被放進stack st.push(nums[i]); } returnans; } Monotonicstack時間複雜度 看到for內又有while迴圈，會覺得時間複雜度到O(n^2)，但其實每個元素都只會被push再被pop一次，因此僅需O(n)的時間複雜度，這也是MonotonicStack的最大優點。

Leetcode對應問題 Leetcode496NextGreaterElementI 這題題目本身敘述不清楚，導致倒讚數很多，但仍舊相當推薦這題作為練習MonotonicStack的基礎題。

題目要求將nums1[index]的值去到Arraynums2上找對應的index，再從該index之後去找比他大的元素。

解法可以拆解為兩部分，先對nums2找每個元素的nextgreaterelement，將結果存起來，接著走訪nums1來將對應的nextgreaterelement找出來。

對nums2找nextgreaterelement，依據前面操作框架，要向右找第一個比他大的元素，代表要從尾端往前走訪處理，而我們要找的是第一個比他大的，代表stacktop必須是所有stack中最小的元素，將stack內資料pop出來要呈現單調遞增。

classSolution{ public: vectornextGreaterElement(vector&nums1,vector&nums2){ if(nums1.size()==0) return{}; unordered_mapgreaterDict; stackst; for(inti=nums2.size()-1;i>=0;i--) { while(!st.empty()&&nums2[i]>st.top()) { st.pop(); } greaterDict[nums2[i]]=st.empty()?-1:st.top(); st.push(nums2[i]); } vectorresult(nums1.size(),-1); inti=0; for(autonum:nums1) { result[i]=greaterDict.count(num)?greaterDict[num]:-1; i++; } returnresult; } }; Leetcode503NextGreaterElementII 此題是MonotonicStack的一個變形，這個array是一個circulararray，只要再度走訪array一遍，基本上將每個元素右手邊可能的元素都走訪過了。

vectornextGreaterElements(vector&nums){ stackst; intsize=nums.size(); vectorresult(size); /*從後面往前走訪，而且將整個array走訪兩遍*/ for(inti=(2*size)-1;i>=0;i--) { while(!st.empty()&&nums[i%size]>=st.top()) { st.pop(); } result[i%size]=st.empty()?-1:st.top(); st.push(nums[i%size]); } returnresult; } Leetcode42TrappingRainWater 這一題是Hard等級的大魔王，但只要你有深度了解MonotonicStack，這題一點都不困難。

題目要求找出積水的水池，如果積水，就代表兩邊的牆高都大於中間底邊，因此可以透過維護一個MonotonicStack，依序放入stack內的元素保持單調遞減（由底端到頂端），一旦新元素要放入stack會破壞單調性，就代表current為水池的右牆高度，就可以計算水池面積了。

與之前單純找到nextgreaterelement不一樣，計算水池面積需要高跟底，因此這邊選擇將index放入stack，而水池的高度則可以透過Array[index]來得到。

另外一個困難點在於，水池的兩邊高可能不一樣，需要取較低的一邊作為水池的高度，水池右邊的高度來自於current，而水池左邊高度該如何得到呢? 得益於monotonicstack裡面存放著單調遞減的高度，所以可以從stack內拿到可能的左牆的高度，只要current放入stack會違反monotonic特性，就必須不斷將stack內元素pop，每個pop出來的都是可能的水底高，此時stack頂端元素就是可能的左牆高。

inttrap(vector&height){ stackst; inti=0,answer=0; intsize=height.size(); while(i=height[i]) { st.push(i++); } else { intt=st.top(); st.pop(); /*ifstackisempty,itmeansthatthereisnoleftsideforwaterpool.*/ if(st.empty()) continue; /** *Waterpoolhasleftsideandrightside. *Youneedtochoosethesmalleroneaswaterpool'sheight. */ intlow_water_level=min(height[st.top()],height[i])-height[t]; intwidth=i-st.top()-1; answer+=(low_water_level*width); } } returnanswer; } 其他本站MonotonicStack解題文章 Leetcode#456132Pattern 參考資料 https://github.com/labuladong/fucking-algorithm/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E5%8D%95%E8%B0%83%E6%A0%88.md https://blog.csdn.net/liujian20150808/article/details/50752861 https://www.cnblogs.com/grandyang/p/8887985.html Lastupdatedon2022-05-1623:06:05星期一 文章導覽 上一篇文章上一篇文章:CS:APPCh7Linking學習筆記下一篇文章下一篇文章:TwoPointer快慢指標篇–陪你刷題 followme linkedin github 近期文章 MaximumSubarraySum問題–陪你刷題 設計一個hashtable–陪你刷題 Leetcode#29DivideTwoIntegers–陪你刷題 Leetcode#647PalindromicSubstrings–陪你刷題 Leetcode#329LongestIncreasingPathinaMatrix–陪你刷題 分類 CS:APP Leetcode linuxkernel 程式設計 自我成長 站內文章搜尋 搜尋關鍵字: 搜尋 彙整 2022年6月 (3) 2022年5月 (6) 2022年1月 (2) 2021年11月 (1) 2021年10月 (2) 2021年9月 (1) 2021年8月 (1) 2021年4月 (2) 2021年3月 (1) 2021年2月 (3) 2021年1月 (5) 2020年12月 (8) 2020年11月 (3) 2020年10月 (1) 2020年9月 (5) 2020年6月 (1) 2019年12月 (1) 2019年10月 (1) 2019年9月 (1) 2019年7月 (1) 2019年6月 (1) 近期文章 MaximumSubarraySum問題–陪你刷題 設計一個hashtable–陪你刷題 Leetcode#29DivideTwoIntegers–陪你刷題 Leetcode#647PalindromicSubstrings–陪你刷題 Leetcode#329LongestIncreasingPathinaMatrix–陪你刷題 分類 CS:APP Leetcode linuxkernel 程式設計 自我成長 近期留言「TopologicalSort–陪你刷題–haogroot'sBlog」於〈Backtracking回溯法–陪你刷題〉發佈留言「Leetcode#329LongestIncreasingPathinaMatrix–陪你刷題–haogroot'sBlog」於〈TopologicalSort–陪你刷題〉發佈留言彙整 2022年6月 2022年5月 2022年1月 2021年11月 2021年10月 2021年9月 2021年8月 2021年4月 2021年3月 2021年2月 2021年1月 2020年12月 2020年11月 2020年10月 2020年9月 2020年6月 2019年12月 2019年10月 2019年9月 2019年7月 2019年6月