Day 13 最小堆疊

2025 iThome 鐵人賽

DAY 0

自我挑戰組

Leetcode自學系列第 13 篇

17th鐵人賽

tina0511

2025-10-01 22:11:21

42 瀏覽

分享至

一開始看到題目時我覺得不難，但思考了一下發現，如果只用一個普通的棧，要取得最小值就得遍歷整個棧，這樣時間複雜度是 O(n)，不符合題目要求的 O(1)。
使用一個主棧儲存所有資料而另一個輔助棧（minStack）專門用來記錄目前的最小值。
當有新元素進來時，如果它比現在的最小值還小，就同時壓入 minStack。
pop 的時候也要同步檢查，如果剛好把最小值移除了，就要從 minStack 裡也移除它。
這樣每次只要看 minStack 的頂端，就能馬上知道目前棧內的最小值。