給定兩個整數陣列
pushed和popped，兩者皆為1到n的排列。判斷這組 push/pop 序列是否為合法的堆疊操作序列。
Example:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true
Intuition
TIP
核心思路：模擬堆疊操作，依序 push 元素，每次 push 後持續檢查棧頂是否與 popped 序列的下一個元素相同，若是則 pop。
- 貪心策略：能 pop 就立刻 pop，因為延遲 pop 不會帶來更好的結果
- 如果模擬結束後堆疊為空，代表序列合法
Approaches
1. In-place: pushed as Stack (O(1) extra) — O(n) / O(1)
- Idea: 重用
pushed陣列前段當堆疊，top當寫入指標，省去額外堆疊 - Time:
O(n) - Space:
O(1)- 不開額外結構
class Solution {
fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean {
var top = 0 // pushed[0 until top) 當作堆疊
var j = 0
for (x in pushed) {
pushed[top++] = x
while (top > 0 && pushed[top - 1] == popped[j]) { top--; j++ }
}
return top == 0
}
}⭐ 2. Stack Simulation (greedy) — O(n) / O(n)
- Idea: 用一個堆疊模擬操作，遍歷 pushed 陣列依序壓入，每次壓入後用 while 迴圈盡可能 pop，最後檢查堆疊是否為空
- Time:
O(n)- 每個元素最多入棧出棧各一次 - Space:
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: 驗證操作序列合法性的題目，直接模擬是最直覺的方法
- Key trick: 貪心地「能 pop 就 pop」是正確策略。用指標
j追蹤 popped 陣列的進度，避免額外空間