算法描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例：
输入： ["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.
算法设计
显然，最小栈算法基于栈这种数据结构实现，是一种空间换时间的思想，常用的方法时使用辅助栈。代码主要由两种设计思路：
- 方案1：辅助栈和数据栈同步
特点：编码简单，不用考虑一些边界情况，就有一点不好：辅助栈可能会存一些“不必要”的元素。
- 方案2：辅助栈和数据栈不同步
特点：由“辅助栈和数据栈同步”的思想，我们知道，当数据栈进来的数越来越大的时候，我们要在辅助栈顶放置和当前辅助栈顶一样的元素，这样做有点“浪费”。基于这一点，我们做一些“优化”，但是在编码上就要注意一些边界条件。
（1）辅助栈为空的时候，必须放入新进来的数；
（2）新来的数小于或者等于辅助栈栈顶元素的时候，才放入，特别注意这里“等于”要考虑进去，因为出栈的时候，连续的、相等的并且是最小值的元素要同步出栈；
（3）出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈。
总结一下：出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。
对比：个人觉得“同步栈”的方式更好一些，因为思路清楚，因为所有操作都同步进行，所以调试代码、定位问题也简单。“不同步栈”，虽然减少了一些空间，但是在“出栈”、“入栈”的时候还要做判断，也有性能上的消耗。
代码实现
- 方案1：同步压入
class MinStack { private Stack<Integer> stackData; private Stack<Integer> stackMin; public MinStack() { stackData = new Stack<>(); stackMin = new Stack<>(); } public void push(int val) { stackData.push(val); if (stackMin.isEmpty() || val < stackMin.peek()) { stackMin.push(val); } else { stackMin.push(stackMin.peek()); } } public void pop() { if (!stackData.isEmpty()) { stackData.pop(); stackMin.pop(); } } public int top() { if (!stackData.isEmpty()) { return stackData.peek(); } throw new RuntimeException("your stack is empty!"); } public int getMin() { if (!stackMin.isEmpty()) { return stackMin.peek(); } throw new RuntimeException("your stack is empty!"); } }
- 方案2：不同步压入
class MinStack { private Stack<Integer> stackData; private Stack<Integer> stackMin; public MinStack() { stackData = new Stack<>(); stackMin = new Stack<>(); } public void push(int val) { // 将必要的元素加入最小栈 if (stackMin.isEmpty() || val <= stackMin.peek()) { stackMin.push(val); } stackData.push(val); } public void pop() { // 数据栈中的元素必须删除 if (!stackData.isEmpty()) { int val = stackData.pop(); // 自动拆箱比较 if (val == stackMin.peek()) { stackMin.pop(); } } } public int top() { if (!stackData.isEmpty()) { return stackData.peek(); } throw new RuntimeException("your stack is empty!"); } public int getMin() { if (!stackMin.isEmpty()) { return stackMin.peek(); } throw new RuntimeException("your stack is empty!"); } }
总结与补充
- 上述两种方案都是使用一个辅助栈保存数据栈每一步对应的最小值。所有操作时间复杂度O(1)，空间复杂度O(n)。
- 两种方案的不同点：
- 入栈，当前值大于最小栈栈顶时：方案1：同步压入最小栈的栈顶；方案2：不压入元素（节省空间）
- 出栈，方案1：同步出栈；方案2：当数据栈顶元素等于最小栈栈顶元素则，最小栈出栈，否则最小栈不出栈。为什么呢？这要看我们的压入规则了，最小栈栈顶一定不会出现小于数据栈的情况，只可能大于或者等于。所以当等于时，我们弹出最小栈栈顶元素，大于时，不弹出最小栈栈顶元素。
