前言

昨天介紹完 Queue 和 Stack，今天來聊聊單調堆疊，看名字可以知道是堆疊的變種，那麼差在哪裡呢？
單調這兩個字指的是讓存放於堆疊中的元素具單調性 ─ 堆疊中的元素為遞增或遞減。
透過維護這種堆疊裡的元素單調性，能夠有效解決特別某一類的問題 ─ 下一個更大(小)的元素。

既然有單調堆疊，那是不是也有單調佇列呢？有的，而且也正好是適用於某一類特定問題，這個留到明天的內容。
先挑堆疊講是因為單調堆疊的實現上相對單調佇列單純，我們可以先透過單調堆疊，了解這種單調性的實現概念。

實現單調性

我們舉個例子，假設有個陣列為 [1,2,3,2,4,1,5]，要維持陣列中是遞增的單調性，我們應該怎麼做？
可以想見，我們應該是要把被「夾起來的數」移除，也就是那些破壞單調性的元素，以上面的例子就是 3,2,4 和 4,1,5，理想清完之後會變成 [1,2,3,4,5]。

以堆疊來實現，所以我們要從陣列的尾部開始遍歷，把元素裝入堆疊，且只裝符合單調性的元素，這樣從堆疊出來的時候，因為是從尾端開始放，出來就會變成從頭開始出來，也就是我們期待的順序。
所以上面這個陣列從 5 開始放入堆疊，接著放入 1，再接著遍歷到 4 ─ 這時候會發現，堆疊頂端的 1 比 4 小，若是放入 4，會破壞陣列的單調性，所以我們得先移除 1，再放入 4，所以確保放入的元素一定會比堆疊頂的小，如此可以維持從底到上，元素大小為大到小，最後出堆疊會是小到大。

// nums = [1,2,3,2,4,1,5]
public int[] implementMonotonous(int nums){
    var stack = new Stack<int>();
    for(var i = nums.Length - 1; i >= 0; i--){
        while(stack.Count > 0 && stack.Peek() <= nums[i]){
            stack.Pop();
        }
        stack.Push(nums[i];
    }
    return Array.Reverse(stack.ToArray());
}

上面的程式碼最後時現、回傳的就是 [1,2,3,4,5] 這樣由小到大的陣列。
這邊有一個要注意的是 stack.Peek() <= nums[i] 這邊是用 <=，因為如果陣列是 [1,2,4,4,5]，我們預期兩個 4 應該都要拿到 5，這邊的比較符號會依題意變動，以下一個更大的數來說的話，這邊就是 <=。

Next Greater Element I

看完單調堆疊的實現，我們來看看怎麼實際應用在題目上，單調堆疊的應用有限，所以看到對應題目要優先想到這是能套用的選項，如這題，找出下一個更大的數字。
這題題目給了我們兩個陣列 nums1 和 nums2，nums1 是 nums2 的子集，所有元素都會在 nums2 中出現。
我們要回傳 nums1 中個元素對應到 nums2 的順序後，下一個(nums2 中往右遍歷)更大的元素，如果往右遍歷不存在更大的元素，則回傳 -1。

直覺地做就是用雙迴圈去遍歷 nums1 和 nums2，然後一一比對下一個更大的數在哪裡，把位置保留起來，最後回傳答案，時間複雜度 O(n^2)。
如果我們有了上面單調堆疊的實現程式碼，我們該怎麼修改，能解決這個問題呢？其實並不難，只要稍微修改就行了。

public class Solution {
    public int[] NextGreaterElement(int[] nums1, int[] nums2) {
        var stack = new Stack<int>();
        var greater = new Dictionary<int,int>();
        for(var i = nums2.Length - 1; i >= 0; i--){
            while(stack.Count > 0 && stack.Peek() <= nums2[i]){
                stack.Pop();
            }
            greater.Add(nums2[i], (stack.Count > 0 ? stack.Peek() : -1));
            stack.Push(nums2[i]);
        }

        var result = new int[nums1.Length];
        for(var i = 0; i < nums1.Length; i++){
            result[i] = greater[nums1[i]];
        }

        return result;
    }
}

我們做的更動就是，我們再放入元素進堆疊的時候，當前堆疊頂端就是最近且比放入元素大的元素，即這題所求，所以我們多做一個 dictionary 去映射 放入元素 : 下一個更大元素。
因為 nums1 必定為 nums2 的子集，透過遍歷 nums2 做出的 dictionary 必定包含所有 nums1 的元素，我們在將映射後的結果重新組成答案陣列，就成功地解開這題了。

乍看之下第一個 for 的迴圈還有一個 while，看似時間複雜度仍是 O(n^2)，但仔細想想，所有元素都只會入堆疊且出堆疊一次，所以實際上還是 O(n) 的時間複雜度，低於暴力解的 O(n^2)。

Next Greater Element II

做完上面那題，會看到 Leetcode 有推薦的相似題目，有個完全題目名稱一樣的，加了個 II 的題目，讓我們多看一些，如何用單調堆疊來處理這類下一個更大元素的問題。

這題的問題基本和上題相同，只差在剩下給一個陣列 nums，找 nums 中的元素下一個最大的元素，差別在於nums的遍歷被定義為環形，即是如果往右走到底後要從新回到頭，直到再次找到自己才能確定有沒有比自己大的元素存在。
最後依照順序回傳所有元素的下一個最大的元素。

這題的基本結構也和上題一樣，差異在於陣列變成環形。
環形的陣列遍歷有一個通用且應該馬上被想到的技巧：將陣列自我串在一起，這樣就能模擬環。
如 [1,2,1] 非環形(上一題情境)我們預期答案是 [2,-1,-1]，環形遍歷下我們應該預期是 [2,-1,2]，而自我串在一起的意思就是把陣列變成 [1,2,1,1,2,1]，這樣就能模擬環多走一圈的情境，得出 [2,-1,2,2,-1,-1]，取前三個 [2,-1,2]，就是預期的答案

直覺的實現如下：

public class Solution {
    public int[] NextGreaterElements(int[] nums) {
        var stack = new Stack<int>();
        var result = new int[nums.Length];
        var numsDuplicated = new int[nums.Length*2];
        for(var i = 0; i < nums.Length; i++){
            numsDuplicated[i] = nums[i];
            numsDuplicated[i + nums.Length] = nums[i];
        }
        for(var i = numsDuplicated.Length - 1; i >= 0; i--){
            while(stack.Count > 0 && stack.Peek() <= numsDuplicated[i]){
                stack.Pop();
            }
            if(i < nums.Length){
                result[i] = stack.Count > 0 ? stack.Peek() : -1;
            }                
            stack.Push(numsDuplicated[i]);
        }

        return result;
    }
}

上面這樣構造了環，佔用了額外的內存空間，那我們有沒有辦法利用其他方式來節省內存空間呢？
有的，因為實際上是自我複製，元素是重複的，在環狀重複的情況下，第 i 個元素就是第 i % 陣列長度 個的元素的值，透過這個認識，我們可以把程式碼修改如下：

public class Solution {
    public int[] NextGreaterElements(int[] nums) {
        var stack = new Stack<int>();
        var result = new int[nums.Length];
        for(var i = nums.Length*2 - 1; i >= 0; i--){
            while(stack.Count > 0 && stack.Peek() <= nums[i%nums.Length]){
                stack.Pop();
            }
            if(i < nums.Length){
                result[i] = stack.Count > 0 ? stack.Peek() : -1;
            }                
            stack.Push(nums[i%nums.Length]);
        }

        return result;
    }
}

透過這個巧妙的置換，我們透過一個餘數計算，節省了空間。
到這裡為止大概是對單調堆疊的實現即討論，別忘了，在處理下一個更大元素類型的問題時候，要想到單調堆疊的這個用法。