155. 最小栈

设计一个支持 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 次

思路为重点.第一次笨方法,list存、取，遍历求最小值。

第二遍时看题解，知道辅助栈的感念，即在每个元素上添加一个变量来保存当前栈中的最小值，也就是说，每次存入时只需要与已存在的最小值比较即可。每次弹出都不影响已存在的栈的最小值。

看到另一种方法，每次存值时存入与当前最小值的差值。即，判断是否存在最小值，不存在，则处理存入值为 与最小值的差值，然后存入。

这样做的好处是不用额外的空间，也就是时间换空间。

以下是改进后的辅助栈代码。