設計一個支持?push?，pop?，top?操作，并能在常數時間內檢索到最小元素的棧。

實現?MinStack?類:

• MinStack()?初始化堆棧對象。
• 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?操作總是在?非空棧?上調用
• push,?pop,?top, and?getMin最多被調用?3 * 104?次

思路：可以搞兩個棧，一個正常，一個從大到小排序的棧，棧頂為當前最小值，用空間換時間

代碼：C#

public class MinStack {

? ? ?Stack<int> stack;

? ? ?Stack<int> minStack;

? ? public MinStack() {

? ? ? ? stack=new Stack<int>();

? ? ? ? minStack=new Stack<int>();

? ? }

? ?

? ? public void Push(int val) {

? ? ? ? stack.Push(val);

? ? ? ? if(minStack.Count==0 ||val<=minStack.Peek())//如果記錄最小值的棧為空或者入棧的值小于等于最小棧的棧頂，即這個要入棧的值為新一個最小值，也要將它入到記錄最小值的棧

? ? ? ? {

? ? ? ? ? ? minStack.Push(val);

? ? ? ? }

? ? }

? ?

? ? public void Pop() {

? ? ? ? int val=stack.Pop();

? ? ? ? if(val==minStack.Peek())//如果出棧的值等于記錄最小值的棧，則也要出棧

? ? ? ? {

? ? ? ? ? ? minStack.Pop();

? ? ? ? }

? ? }

? ?

? ? public int Top() {

? ? ? ? return stack.Peek();

? ? }

? ?

? ? public int GetMin() {

? ? ? ? return minStack.Peek();

? ? }

}