上文我們介紹了的方案一，本文繼續討論方案二：
【 題目 】
實現一特殊的棧，在實現棧的基本功能的基礎上，再實現返回棧中最小元素的操作。
【 要求 】
1 . pep 、 push 、 getMin 操作的時間複雜度都是 O ( 1 ) 。
2 ．設計的棧類型可以使用現成的棧結構。
【 解答 】
在設計上我們使用兩個棧，一個棧用來保存當前棧中的元素，其功能和一個正常的棧沒有區別，這個棧記為 stackData ；另一個棧用於保存每一步的最小值，這個棧記為 stackMin 。具體的實現方式有兩種。
第二種設計方案如下。
· 壓入數據規則
假設當前數據為 newNum ，先將其壓入 stackdata 。然後判斷 stackMin 是否為空。
如果為空，則 newN um 也壓入 stackMin ；如果不為空，則比較 n ewNuw和stackMin 的棧頂元素中哪一個更小：
如果 newNum 更小或兩者相等，則 newNum 也壓入 stackMin ；如果 stackMin 中棧頂元紊小，則把 stackMin 的棧頂元素重複壓入 stackMin ，即在棧頂元素上再壓入一個棧頂元素．
舉例：依次壓入 3 、 4 、 5 、 1 、 2 、 1 的過程中， stackData 和 stackMin 的變化如圖1- 2 所示。
圖1-2
· 彈出數據規則
在 stackData 中彈出數據，彈出的數據記為 value ；彈出 stackMin 中的棧頂；返回 value 。很明顯可以看出，壓入與彈出規則是對應的。
· 查詢當前棧中的目小值操作
由上文的壓入數據規則和彈出數據規則可知，stackMin 始終記錄看 stackData 中的最小值，所以 stackMin 的棧頂元素始終是當前 stackData 中的最小值。
方案二的代碼實現如 Mystack2類所示：
【點評】
方案一和方案二其實都是用 stack Min棧保存著 stack Data每一步的最小值。共同點是所有操作的時間複雜度都為O(1)、空間複雜度都為O(n)。區別是:方案一中 stack Min壓入時稍省空間,但是彈出操作稍費時間;方案二中 stackmin壓入時稍費空間,但是彈出操作稍省時間。
更多技術交流，歡迎小夥伴們可以一起交流一下哦
CSDN社群火爆招募中：https://blog.csdn.net/CSDNedu/article/details/80063505?utm_source=zwqt
閱讀更多 CSDN學院 的文章
