設(shè)計(jì)一個(gè)支持?push?，pop?，top?操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

實(shí)現(xiàn)?MinStack?類:

• MinStack()?初始化堆棧對(duì)象。

• void push(int val)?將元素val推入堆棧。

• void pop()?刪除堆棧頂部的元素。

• int top()?獲取堆棧頂部的元素。

• int getMin()?獲取堆棧中的最小元素。

?

示例 1:

輸入：["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]輸出：[null,null,null,null,-3,null,0,-2]解釋：MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); ? --> 返回 -3. minStack.pop(); minStack.top(); ? ? ?--> 返回 0. minStack.getMin(); ? --> 返回 -2.

?

提示：

• -231?<= val <= 231?- 1

• pop、top?和?getMin?操作總是在?非空棧?上調(diào)用

• push,?pop,?top, and?getMin最多被調(diào)用?3 * 104?次

思路為重點(diǎn).第一次笨方法,list存、取，遍歷求最小值。

第二遍時(shí)看題解，知道輔助棧的感念，即在每個(gè)元素上添加一個(gè)變量來保存當(dāng)前棧中的最小值，也就是說，每次存入時(shí)只需要與已存在的最小值比較即可。每次彈出都不影響已存在的棧的最小值。

看到另一種方法，每次存值時(shí)存入與當(dāng)前最小值的差值。即，判斷是否存在最小值，不存在，則處理存入值為 與最小值的差值，然后存入。

這樣做的好處是不用額外的空間，也就是時(shí)間換空間。

以下是改進(jìn)后的輔助棧代碼。