Description
給定兩個無重複元素的陣列
nums1和nums2，其中nums1是nums2的子集。對nums1中的每個元素，在nums2中找到它右邊第一個比它大的元素。不存在則回傳 -1。
Example:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1]
Intuition#
核心思路：用單調遞減 Stack 預處理
nums2中每個元素的下一個更大值，存入 HashMap，再查詢nums1。
- 暴力法對
nums1每個元素都要在nums2中掃描右邊，O(n * m) - 單調 Stack 可以一次遍歷
nums2就求出所有元素的 Next Greater Element
Approaches#
1: Brute Force#
- 概念: 對
nums1每個元素，在nums2中找到其位置，然後往右掃描找更大的 - 時間複雜度:
O(n * m)- n 為 nums1 長度，m 為 nums2 長度 - 空間複雜度:
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#
- 概念: 遍歷
nums2，維護單調遞減 Stack。當前元素比棧頂大時，棧頂的 Next Greater 就是當前元素。將結果存入 Map，最後查詢nums1。 - 時間複雜度:
O(n + m)- 每個元素最多進出 Stack 一次 - 空間複雜度:
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 問題的標準工具
- 關鍵技巧: 維護遞減 Stack，遇到更大元素時彈出並記錄映射；此模式可推廣到 LC 503（循環陣列）和 LC 739（每日溫度）