496. Next Greater Element I

──────────────────────────────────────────────────────────────────────

496. Next Greater Element I

給兩個陣列，nums1 是 nums2 的子集，所有數字互不重複。對 nums1 的每個數字，要在 nums2 裡找到它，然後回報它右邊第一個比它大的數；沒有的話就是 -1。

nums1 = [4,1,2], nums2 = [1,3,4,2]  →  [-1, 3, -1]

這一題是 Monotonic 的題目，但是它的變形其實滿難的，會建議先從 739. Daily Temperatures 熟悉後，再來處理這個。

思路

nums1 和 nums2 之間的順序是隨機的，並沒有任何關聯 —— 所以第一件事一定是把 nums1 的數字對應回 nums2 的世界。

我的第一個想法是：如果我知道 nums1 每個數字在 nums2 的位置，接著我只要從該位置出發向右找，找出下一個更大的數字就好。要注意的是有可能沒有下一個更大的數字，所以一開始預設的答案用 -1。

這個做法是對的，nums2 最長 1000，$O(n\times m)$ 跑得完。但它的浪費很明顯：nums1 的每個數字都各自往右重掃一次，那些區間大量重疊。

換個問法：一次把 nums2 全部算完

與其被問一個算一個，不如先把 nums2 每個位置的答案都算好，之後 nums1 只是查表。

要一次算完，關鍵是從右往左走，並且維護一個棧，裡面放的是「我右邊那些還可能當別人答案的數」。走到位置 i 的時候：

• 把棧裡所有小於等於 nums2[i] 的都彈掉。因為它們比我小、又在我右邊，對我左邊的任何人來說都沒用了 —— 誰要找「右邊第一個更大的」，都會先撞到我這一關
• 彈完之後，棧頂就是我的答案：它是右邊還活著的最近的一個，而且比我大
• 棧空掉就代表右邊沒有比我大的，答案是 -1

彈掉的規則保證了棧從頂到底是遞增的，這就是單調棧。

但 nums1 只有數字，沒有位置

算完之後還有一個接口問題：我算出來的是「每個位置的答案」，可是 nums1 給我的只有數字。

所以要再用一張 Hash Table 把「數字 → 那個位置的答案」對起來。因為題目保證數字不重複，這個對應才會唯一。

（單調棧在這題有兩種方向的寫法，下面兩版都寫出來 —— 差別在答案是在 peek 的時候產生，還是在 pop 的時候產生。）

解題方向

方法一：查位置後往右找

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        table = dict()
        for i, num in enumerate(nums2):
            table[num] = i
        
        res = []
        for num in nums1:
            idx = table[num]
            ans = -1
            for i in range(idx, len(nums2)):
                if nums2[i] > num:
                    ans = nums2[i]
                    break
            res.append(ans)
        
        return res

table[num] 敢直接查不怕 KeyError，靠的是題目的兩個保證：nums1 是 nums2 的子集（查得到）、數字互不重複（對應唯一）。面試時這兩句要主動講出來。

方法二：從右往左，看棧頂

第一個步驟，先把 nums2 每個位置右側的下一個更大值找出來：

        n = len(nums2)
        tmp = [-1] * n
        s = []
        for i in range(n - 1, -1, -1):
            while s and s[-1] <= nums2[i]:
                s.pop()
            if s:
                tmp[i] = s[-1]
            s.append(nums2[i])

用題目的例子走一遍（從右往左）：

i=3 值=2   棧空          tmp[3] = -1    棧 = [2]
i=2 值=4   彈掉 2        tmp[2] = -1    棧 = [4]
i=1 值=3   棧頂是 4      tmp[1] = 4     棧 = [4, 3]
i=0 值=1   棧頂是 3      tmp[0] = 3     棧 = [4, 3, 1]

第二個步驟，把 nums2 每個數字對應的答案，透過 Hash Table 記錄下來。這裡可以一次多做一步：我們在記錄每個位置的下一個更大值時，tmp 的每個位置和 nums2 是有對應的，所以直接把 nums2[i] → tmp[i] 存起來就好。

最後就可以一起完成：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums2)
        tmp = [-1] * n
        s = []
        for i in range(n - 1, -1, -1):
            while s and s[-1] <= nums2[i]:
                s.pop()
            if s:
                tmp[i] = s[-1]
            s.append(nums2[i])
        m = {}
        for i in range(n):
            m[nums2[i]] = tmp[i]
        res = []
        for num in nums1:
            res.append(m[num])
        return res

方法三：從左往右，pop 的瞬間就是答案

同樣是單調棧，但走的方向反過來。這時候棧裡裝的不是「候選答案」，而是「還在等答案的數」：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:

        table = {}   # 數字 → 它的下一個更大元素
        stack = []   # 還在等下一個更大元素的數字

        for num in nums2:
            while stack and stack[-1] < num:
                table[stack.pop()] = num
            stack.append(num)

        return [table.get(num, -1) for num in nums1]

核心是這一句：j 被彈出的那一刻，當前的 num 就是 j 的下一個更大元素。

為什麼是「下一個」而不只是「某一個更大的」？因為 j 是更早被推進去的，而且一路活到現在都沒被彈出 —— 沒被彈出就代表 j 和 num 之間的每一個數都不比 j 大，只要有任何一個比它大，j 早就在那一步被彈掉了。所以 num 是它右邊第一個比它大的。「第一個」這個性質不是額外檢查出來的，是棧的維護方式自動保證的。

走一遍同一個例子：

push 1   → 棧 = [1]
3 進來   → 彈出 1，記下 table[1] = 3   → 棧 = [3]
4 進來   → 彈出 3，記下 table[3] = 4   → 棧 = [4]
2 進來   → 2 < 4，不彈                  → 棧 = [4, 2]

結束，棧裡還剩 [4, 2] → 這兩個永遠沒等到，答案是 -1
table = {1: 3, 3: 4}

棧裡剩下的，就是沒有下一個更大元素的那些。 不用特別處理，table.get(num, -1) 查不到就給 -1。

這一版也不需要 tmp 陣列和第二張表 —— 因為數字保證唯一，直接用數值當棧和表的 key 就好，不用繞經位置。

兩個方向的對照

	棧裡裝什麼	答案在哪一刻產生	需要位置嗎
從右往左（方法二）	右邊還可能當答案的候選	peek 棧頂	要，所以有 tmp 和第二張表
從左往右（方法三）	還在等答案的數	pop 的瞬間	不用，直接存數值

寫單調棧的時候先問自己一句：「pop 的那一刻，我知道了什麼？」 1762 的 pop 代表「這棟被擋住了」所以丟掉；這題方法三的 pop 代表「這個數等到了」所以寫進答案。同一個機制，差別只在那一刻要記什麼。

複雜度

方法一：查位置後往右找

• 時間 $O(n\times m)$ — 建表 $O(m)$，之後 nums1 的每個數最壞要從自己的位置掃到 nums2 結尾
• 空間 $O(m)$ — table 為 nums2 的每個數字存一個位置

方法二、方法三：單調棧

• 時間 $O(n+m)$ — nums2 掃一遍，每個數最多進棧一次、出棧一次；nums1 每個數查表 $O(1)$
• 空間 $O(m)$ — 棧和表都是 $O(m)$（方法二多一個 tmp 陣列，同樣是 $O(m)$）

其中 $n$ 是 nums1 的長度、$m$ 是 nums2 的長度（題目保證 $n\le m$），回傳的 res 不計入額外空間。

單調棧省的純粹是時間，空間跟方法一是同一個等級。 最壞情況是 nums2 嚴格遞減而且 nums1 就是整個 nums2 —— 每個數往右掃都掃到底還找不到；反過來如果 nums2 遞增，方法一的內層迴圈第一步就 break，兩版差不多快。方法一不是總是慢，是最壞情況慢。