Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

本篇要來探討的是 Monotonic Stack。

什麼是 Monotonic Stack

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

• 每次加新元素到 stack 時， stack 內的元素都保持 Monotonic (可以是單調遞增或是單調遞減)。
• 搭配 Array 使用，Array 的每個元素必定會被放入 stack 中。一旦出了 stack ，就不會再被放進去。

該如何理解 Monotonic Stack

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

Monotonic Stack 內可以放身高，也可以放對應的座號。

Monotonic Stack 操作框架

要操作 Monotonic Stack ，就必須謹記以下性質:

1. Monotonic Stack 內的元素一定維持 monotonic 特性 (單調遞增或單調遞減) 。
2. 每個元素都會加入 stack ，如果加入新元素會破壞 monotonic ，就必須將 stack 頂端元素移除，不斷移除 stack 頂端元素直到不違反 monotonic ，接著再加入元素。
3. Monotonic Stack 可以幫助找到向左/向右走訪第一個比當前元素小/大的元素，左/右跟小/大總共有四種組合。

如果要向左找第一個比 input 元素小的元素，以下圖為例，

從 Array 的起點開始走訪並依序加入 stack ，stack 內元素都維持單調遞增的排序，直到準備放入 7 時，放入 7 會破壞單調遞增，因此必須 pop 元素直到可以維持單調遞增，當 7 可以放入 stack 之前，此時 stack 頂端元素即是第一個比 7 小的元素。
Stack 頂端的元素應該保持是向左找第一個比 input 小的元素，且 top 會是 stack 內最大的，(要找的是第一個比 input 元素小的，因此越小的應該越要在 stack 底部 ，才不會輕易被 pop out ) ，stack 內的元素 pop 出來的結果就應該遞減。

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

Monotonic Stack 框架程式碼

下面展示的例子是尋找每個 input 元素其右手邊第一個比他大的元素。由於是找右手邊的元素，所以從 Array 尾端往前依序處理。

vector<int> nextGreaterElement(vector<int>* nums)
{
    vector<int> ans(nums.size());
        stack<int> st;
        // 從矩陣尾端往前走訪
        for (int i=nums.size()-1; i>=0; i--)
        {
            /**
             * 要維持 stack 內都是比新元素還要大，且越接近 stack bottom 元素
             * 越大，stack top 元素就不能小於要 push 進 stack 的元素，
             * 如果小於就移除 top 元素。
             */
            while (!st.empty() && nums[i] >= st.top())
            {
                st.pop()
            }
            // 當 stack 內為空，代表找不到比他大的
            // 若 stack 不為空，stack top 元素就是
            // 第一個比他大的元素
            ans[i] = st.empty()? -1 : st.top();
            // 每個元素一定會被放進 stack
            st.push (nums[i]);
        }
        return ans;
}

Monotonic stack 時間複雜度

看到 for 內又有 while 迴圈，會覺得時間複雜度到 O (n^2) ，但其實每個元素都只會被 push 再被 pop 一次，因此僅需 O(n) 的時間複雜度，這也是 Monotonic Stack 的最大優點。

Leetcode 對應問題

Leetcode 496 Next Greater Element I

這題題目本身敘述不清楚，導致倒讚數很多，但仍舊相當推薦這題作為練習 Monotonic Stack 的基礎題。
題目要求將 nums1[index] 的值去到 Array nums2 上找對應的 index，再從該 index 之後去找比他大的元素。

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

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

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() == 0)
            return {};
        unordered_map<int, int> greaterDict;
        stack<int> st;

        for (int i= 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]);
        }
        vector<int>result(nums1.size(), -1);
        int i=0;
        for (auto num:nums1)
        {
            result[i] = greaterDict.count(num)?greaterDict[num]:-1;
            i++;
        }
        return result;
    }
};

Leetcode 503 Next Greater Element II

此題是 Monotonic Stack 的一個變形，這個 array 是一個 circular array ，只要再度走訪 array 一遍，基本上將每個元素右手邊可能的元素都走訪過了。

    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        int size = nums.size();
        vector<int> result(size);
        /* 從後面往前走訪，而且將整個 array 走訪兩遍 */
        for (int i=(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]);
        }
        return result;
    }

Leetcode 42 Trapping Rain Water

這一題是 Hard 等級的大魔王，但只要你有深度了解 Monotonic Stack ，這題一點都不困難。

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

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

另外一個困難點在於，水池的兩邊高可能不一樣，需要取較低的一邊作為水池的高度，水池右邊的高度來自於 current ，而水池左邊高度該如何得到呢?

得益於 monotonic stack 裡面存放著單調遞減的高度，所以可以從 stack 內拿到可能的左牆的高度，只要 current 放入 stack 會違反 monotonic 特性，就必須不斷將 stack 內元素 pop ，每個 pop 出來的都是可能的水底高，此時 stack 頂端元素就是可能的左牆高。

    int trap(vector<int>& height) {
        stack<int> st;
        int i = 0, answer = 0;
        int size = height.size();

        while (i<size)
        {
            if (st.empty() || height[st.top()] >= height[i])
            {
                st.push(i++);
            }
            else
            {
                int t = st.top();
                st.pop();
                /* if stack is empty, it means that there is no left side for water pool. */
                if (st.empty())
                    continue;
                /** 
                 * Water pool has left side and right side.
                 * You need to choose the smaller one as water pool's height.
                 */
                int low_water_level = min(height[st.top()], height[i]) - height[t];
                int width = i - st.top() - 1;
                answer += (low_water_level * width);
            }
        }
        return answer;
    }

其他本站 Monotonic Stack 解題文章

1. Leetcode #456 132 Pattern

參考資料

1. 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
2. https://blog.csdn.net/liujian20150808/article/details/50752861
3. https://www.cnblogs.com/grandyang/p/8887985.html

Last updated on 2022-05-16 23:06:05 星期一