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