算法描述
设计一个支持 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：当数据栈顶元素等于最小栈栈顶元素则，最小栈出栈，否则最小栈不出栈。为什么呢？这要看我们的压入规则了，最小栈栈顶一定不会出现小于数据栈的情况，只可能大于或者等于。所以当等于时，我们弹出最小栈栈顶元素，大于时，不弹出最小栈栈顶元素。
巨人的肩膀：
网友评论