題目

設計一個棧, 在實現棧的基本功能基礎上, 還能夠返回棧中最小的元素

算法分析

最直觀的想法, 就是直接使用棧, 每次要想拿到最小元素時, 就從棧A中全部出棧, 然後尋找其中的最小元素, 之後在將元素全部壓入棧A, 要實現這個全部取出在全部壓入的操作, 顯然需要一個臨時的數組結構, 最好也是棧結構.

那麼, 既然用到了另外的棧, 我們又何必做全部出棧再全部入棧這麼費時的操作, 將另一個棧用作保存最小元素不就好了麼.

到這裡, 我們決定使用兩個棧來實現這個功能, 一個棧用於保存數據, 一個棧用於保存當前的最小值, 新的問題又來了, 數據棧的入出自不必說, 那麼最小值的棧該如何實現入棧和出棧的操作, 才能保證每次棧頂都是當前的最小值呢?

最小值棧的設計思路一:

數據入棧時, 將最小值保存在最小值棧中, 若最小值無更新, 則重複入最小值棧, 這樣在數據出棧時, 最小值棧跟著出棧即可.

其壓入數據的具體規則應如下(若當前壓入數據num):

1. 將num如數據棧
2. 判斷最小值棧是否為空
3. 若最小值棧為空, 則num入最小值棧
4. 若最小值棧不為空, 則判斷num與最小值棧棧頂元素min的大小
5. 若min >= num, 則num入最小值棧
6. 若min < num, 則min入最小值棧

其壓入數據過程如圖所示:

出棧操作與入棧操作對應, 每次數據棧出棧時, 最小值棧也同步出棧即可

簡單的Java代碼實現如下, 代碼不夠完善, 僅提供思路:

最小值棧的設計思路二:

上面的思路導致兩個棧大小相等, 顯然最小值棧中存在很多重複的元素, 如何節省最小值棧的空間呢?

將最小值棧頂保存當前棧的最小值, 若有新數據入棧時, 判斷其與最小值棧棧頂元素大小, 判斷是否需要更新最小值, 若新值更小或者相等的話, 則壓入最小值棧(相等也入棧是因為出棧的時候, 可以直接出棧, 不用顧慮太多), 如此即可使的最小值棧棧頂元素為當前棧的最小值

其壓入數據的具體規則應如下(若當前壓入數據num):

1. 將num入數據棧
2. 判斷最小值棧是否為空
3. 若最小值棧為空, 則num入最小值棧, 不做操作
4. 若最小值棧不為空, 則將num與最小值棧棧頂元素min進行比較
5. 若min>=num, 則將num入棧
6. 若min

其壓入數據過程如下圖所示:

壓入數據的規則有了, 那麼彈出數據的規則也就有了, 因為總是將更小或相等的元素壓入最小值棧, 所以最小值棧中的元素上面的總是小於等於下面的元素, 故在彈出數據時進行判斷即可, 若是最小值則彈出, 具體如下(彈出數據num):

1. 判斷num與最小值棧棧頂元素min的大小
2. 若 num > min, 不做操作
3. 若num == min, 彈出最小值棧棧頂元素(因為入棧時沒出現一個, 都入棧一次, 所以出棧時每次也都要出棧了)
4. 若num < min, 異常了吧, 咱們是將最小的壓入棧頂, 若出現這種情況, 傷心

簡單的Java代碼實現如下, 代碼不夠完善, 僅提供思路:

當然, 並不是思路二就比思路一要號, 思路二雖然節省了空間, 但是在出棧操作時要進行判斷, 稍費些時間.

閱讀更多 牛牛的編程之路 的文章

關鍵字: 編程語言 技術 設計