設計一個支援
push、pop、top和getMin的堆疊，所有操作必須在O(1)時間內完成。
Example:
Input: [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”], [[],[-2],[0],[-3],[],[],[],[]] Output: [null,null,null,null,-3,null,0,-2]
Intuition
TIP
核心思路：用一個輔助堆疊同步記錄「截至目前為止的最小值」，使 getMin 能在 O(1) 內回傳。
- 普通堆疊的 push/pop/top 都是 O(1)，難點在於 O(1) 取得最小值
- 最小值會隨著 push/pop 改變，所以需要追蹤每個「狀態」下的最小值
- 每次 push 時，輔助堆疊壓入
min(新值, 當前最小值)，pop 時同步彈出
Approaches
1. Single Stack of Pairs — O(1) / O(n)
- Idea: 堆疊中每個元素存
Pair(value, currentMin)，將值和對應最小值綁在一起 - Time: 所有操作
O(1) - Space:
O(n)- 每個元素多存一個最小值
class MinStack() {
private val stack = ArrayDeque<Pair<Int, Int>>()
fun push(`val`: Int) {
val currentMin = if (stack.isEmpty()) `val` else minOf(`val`, stack.last().second)
stack.addLast(`val` to currentMin)
}
fun pop() {
stack.removeLast()
}
fun top(): Int {
return stack.last().first
}
fun getMin(): Int {
return stack.last().second
}
}⭐ 2. Two Stacks — O(1) / O(n)
- Idea: 主堆疊存數值，輔助堆疊
minStack只在新值 <= 當前最小值時才壓入，節省空間 - Time: 所有操作
O(1) - Space:
O(n)- 最壞情況輔助堆疊和主堆疊一樣大，但平均更省
class MinStack() {
private val stack = ArrayDeque<Int>()
private val minStack = ArrayDeque<Int>()
fun push(`val`: Int) {
stack.addLast(`val`)
val currentMin = if (minStack.isEmpty()) `val` else minOf(`val`, minStack.last())
minStack.addLast(currentMin)
}
fun pop() {
stack.removeLast()
minStack.removeLast()
}
fun top(): Int {
return stack.last()
}
fun getMin(): Int {
return minStack.last()
}
}WARNING
注意 minStack 必須和主堆疊同步 push/pop。如果只在「新值更小時」才 push 到 minStack 且 pop 時只在棧頂等於最小值才 pop，需要特別處理重複最小值的情況（用 <= 而非 <）。上面的實作每次都同步操作，更安全。
🔑 Takeaways
- Pattern: 需要 O(1) 追蹤額外資訊時，考慮用輔助資料結構同步維護
- Key trick: 輔助堆疊記錄「歷史最小值」的技巧可以推廣到追蹤最大值、頻率等場景