`Min Stack`：支持`getMin()`操作的栈，前不久刚写过O(1)时间，O(N)额外空间的解法，并扩展到了Min Queue。详见Queue With MAX

# 详细步骤

`Push(x)`:

（1）如果x >= minEle，则直接将x入栈
（2）如果x < minEle,将`2*x - minEle`入栈，并将minEle = x，例如之前的minEle = 3，现在push(2)，则将minEle更新为2，并讲2*2 - 3 = 1入栈。

`Pop()`:

`注意`

minEle永远是栈中最小值的真实值。

# 实例

## Push(x)

1. Number to be Inserted: 3, Stack is empty, so insert 3 into stack and minEle = 3.
2. Number to be Inserted: 5, Stack is not empty, 5> minEle, insert 5 into stack and minEle = 3.
3. Number to be Inserted: 2, Stack is not empty, 2< minEle, insert (2 * 2-3 = 1) into stack and minEle = 2.
4. Number to be Inserted: 1, Stack is not empty, 1< minEle, insert (2 * 1-2 = 0) into stack and minEle = 1.
5. Number to be Inserted: 1, Stack is not empty, 1 = minEle, insert 1 into stack and minEle = 1.
6. Number to be Inserted: -1, Stack is not empty, -1 < minEle, insert (2 * -1 – 1 = -3) into stack and minEle = -1.

## Pop()

1. Initially the minimum element minEle in the stack is -1.
2. Number removed: -3, Since -3 is less than the minimum element the original number being removed is minEle which is -1, and the new minEle = 2 * -1 – (-3) = 1
3. Number removed: 1, 1 == minEle, so number removed is 1 and minEle is still equal to 1.
4. Number removed: 0, 0< minEle, original number is minEle which is 1 and new minEle = 2 * 1 – 0 = 2.
5. Number removed: 1, 1< minEle, original number is minEle which is 2 and new minEle = 2 * 2 – 1 = 3.
6. Number removed: 5, 5> minEle, original number is 5 and minEle is still 3