給定兩個無重複元素的陣列
nums1和nums2，其中nums1是nums2的子集。對nums1中的每個元素，在nums2中找到它右邊第一個比它大的元素。不存在則回傳 -1。
Example:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1]
Intuition
TIP
核心思路：用單調遞減 Stack 預處理 nums2 中每個元素的下一個更大值，存入 HashMap，再查詢 nums1。
- 暴力法對
nums1每個元素都要在nums2中掃描右邊，O(n * m) - 單調 Stack 可以一次遍歷
nums2就求出所有元素的 Next Greater Element
Approaches
1. Brute Force — O(n * m) / O(1)
- Idea: 對
nums1每個元素，在nums2中找到其位置，然後往右掃描找更大的 - Time:
O(n * m)- n 為 nums1 長度，m 為 nums2 長度 - Space:
O(1)- 不計輸出
class Solution {
fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
val result = IntArray(nums1.size)
for (i in nums1.indices) {
var found = false
var greater = -1
for (j in nums2.indices) {
if (nums2[j] == nums1[i]) found = true
if (found && nums2[j] > nums1[i]) {
greater = nums2[j]
break
}
}
result[i] = greater
}
return result
}
}⭐ 2. Monotonic Stack + HashMap — O(n + m) / O(m)
- Idea: 遍歷
nums2，維護單調遞減 Stack。當前元素比棧頂大時，棧頂的 Next Greater 就是當前元素。將結果存入 Map，最後查詢nums1。 - Time:
O(n + m)- 每個元素最多進出 Stack 一次 - Space:
O(m)- Stack 和 HashMap
class Solution {
fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
val map = HashMap<Int, Int>()
val stack = ArrayDeque<Int>()
for (num in nums2) {
while (stack.isNotEmpty() && stack.peek() < num) {
map[stack.pop()] = num
}
stack.push(num)
}
return IntArray(nums1.size) { map.getOrDefault(nums1[it], -1) }
}
}🔑 Takeaways
- Pattern: 單調 Stack 是解決 Next Greater / Next Smaller 問題的標準工具
- Key trick: 維護遞減 Stack，遇到更大元素時彈出並記錄映射；此模式可推廣到 LC 503（循環陣列）和 LC 739（每日溫度）