496. Next Greater Element I

Next Greater Element I

題目描述：nums1 是 nums2 的子集（不含重複元素）。對 nums1 中的每個元素，找出它在 nums2 中出現位置右邊的第一個更大的元素；若不存在，則回傳 -1。

解題思路：

暴力解法是對 nums1 的每個元素在 nums2 中線性搜尋，複雜度為 O(m × n)。更佳的做法是預先用單調遞減棧處理 nums2，建立一個 hashmap nextGreater{值 → 下一個更大值}，再查詢 nums1。

處理 nums2 的步驟：

1. 初始化空棧 stk 和 hashmap map。
2. 遍歷 nums2 每個元素 x：
   • 若 x 大於棧頂元素，表示 x 是棧頂的「下一個更大元素」→ 彈出棧頂 top，設 map[top] = x，重複直到棧空或棧頂 ≥ x。
   • 將 x 推入棧。
3. 遍歷結束後棧中剩餘的元素，在 nums2 中沒有更大的元素，設 map[top] = -1。
4. 最後查詢 nums1 的每個元素，從 map 取值即為答案。

以 nums1 = [4,1,2], nums2 = [1,3,4,2] 為例：

• 遍歷 nums2：1 入棧；3 > 1 → map[1]=3，3 入棧；4 > 3 → map[3]=4，4 入棧；2 < 4，2 入棧。
• 棧剩 [4, 2]：map[4]=-1, map[2]=-1。
• 查詢 nums1：map[4]=-1, map[1]=3, map[2]=-1 → 回傳 [-1, 3, -1]。

時間複雜度：O(m + n) — 預處理 nums2 需 O(n)（每個元素最多入棧和出棧各一次），查詢 nums1 需 O(m)（m 為 nums1 長度，n 為 nums2 長度）。

空間複雜度：O(n) — hashmap 和棧均最多儲存 nums2 的所有元素。

替代方法

方法一：暴力雙迴圈

對 nums1 的每個元素，先找其在 nums2 中的位置，再向右線性掃描找第一個更大的元素。

時間複雜度：O(m × n)｜空間複雜度：O(1)（不含輸出）

當 m 和 n 較小時可接受，但不適合大輸入。

方法二：二分搜尋（不適用）

nums2 無序，二分搜尋無法直接應用於「找下一個更大值」的問題。若陣列有序，才可考慮二分。

方法三：單調棧 + hashmap（推薦，本題解法）

預處理一次 nums2 建立完整映射，查詢 O(1)。整體 O(m + n)，是最優解法。

時間複雜度：O(m + n)｜空間複雜度：O(n)

延伸問題

1. Next Greater Element II（LeetCode 503）：若陣列為循環陣列，每個元素可繼續向右循環搜尋，應如何修改？提示：遍歷陣列兩次並用 i % n 取索引，棧改存索引而非值。

2. Next Greater Element III（LeetCode 556）：給定整數 n，找重排其數字後比 n 大的最小整數。此題本質是「下一個排列」問題，與本題思路不同但共享「找更大」的核心概念。

3. 若 nums2 允許重複元素：本題保證 nums2 不含重複，若有重複元素，hashmap 的 key 衝突應如何處理？提示：改用索引作為 key（nextGreater[index] = value），或對每個值分別維護多個答案。