今天來看的是單調棧(monotonic stack)。

stack 的性質大家應該清楚（後進先出），這邊就不多做解釋。單調棧是在 stack 上多加了一層限制：維護的 stack 必須是遞增或遞減，如果違反規則就一路 pop 出去，直到滿足上述條件為止。

拿來當範例的 496. Next Greater Element I，會檢視陣列每個位置中的元素，然後求出在自己後面、比自己大的下一個數。直觀的算法就是暴力解，直接多次遍歷陣列 O(n) * O(n) = O(n^2)。

如果要使用單調棧的話，這邊要利用一點小技巧，從後往前遍歷，並維持一個遞減的 stack。如果元素有辦法被 push 進 stack 代表有解，沒辦法的話則表示後方沒有比自己更大的數，因此 stack 中所有元素都會被 pop 掉，自己再被 push 進去。

複雜度的話，單次的平均成本比較難計算，不過就 stack 的操作來看，每個 item 最多被 push 一次，也最多被 pop 一次。如果有一次的搜尋成本特別高遍歷了整個 stack，下次的成本就會變成常數，所以複雜度應該在 O(n) 之內吧（如果有錯歡迎指正）。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1]*len(nums1)
        dic = {nums2[-1]: -1}

        s = [nums2[-1]]

        for i in nums2[:-1][::-1]:
            if i > s[0]:
                s = [i]
                dic[i] = -1
            else:
                while s[-1] < i:
                    s.pop()
                dic[i] = s[-1]
                s.append(i)

        for i in range(len(nums1)):
            res[i] = dic[nums1[i]]

        return res

另一種沒那麼直觀的寫法：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic = {}
        stack = []

        for item in nums2:
            while stack and item > stack[-1]:
                tail = stack.pop()
                dic[tail] = item

            stack.append(item)

        for item in stack:
            dic[item] = -1

        res = [0 for _ in range(len(nums1))]

        for idx, num in enumerate(nums1):
            res[idx] = dic[num]

        return res

• 單調棧
  • 496. Next Greater Element I

• Total count: 6
  • 待補中 307. Range Sum Query - Mutable