Description
給定兩個整數陣列
pushed和popped，兩者皆為1到n的排列。判斷這組 push/pop 序列是否為合法的堆疊操作序列。
Example:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true
Intuition#
核心思路：模擬堆疊操作，依序 push 元素，每次 push 後持續檢查棧頂是否與 popped 序列的下一個元素相同，若是則 pop。
- 貪心策略：能 pop 就立刻 pop，因為延遲 pop 不會帶來更好的結果
- 如果模擬結束後堆疊為空，代表序列合法
Approaches#
⭐1: 堆疊模擬（貪心）#
- 概念: 用一個堆疊模擬操作，遍歷 pushed 陣列依序壓入，每次壓入後用 while 迴圈盡可能 pop，最後檢查堆疊是否為空
- 時間複雜度:
O(n)- 每個元素最多入棧出棧各一次 - 空間複雜度:
O(n)- 堆疊最多存 n 個元素
class Solution {
fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean {
val stack = ArrayDeque<Int>()
var j = 0
for (x in pushed) {
stack.addLast(x)
while (stack.isNotEmpty() && stack.last() == popped[j]) {
stack.removeLast()
j++
}
}
return stack.isEmpty()
}
}🔑 Takeaways#
- Pattern: 驗證操作序列合法性的題目，直接模擬是最直覺的方法
- 關鍵技巧: 貪心地「能 pop 就 pop」是正確策略。用指標
j追蹤 popped 陣列的進度，避免額外空間