设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
入栈 3
| | min = 3
| |
|_3_|
stack
入栈 5
| | min = 3
| 5 |
|_3_|
stack
入栈 2
| 2 | min = 2?
| 5 |
|_3_|
stack
如果只用一个变量就会遇到一个问题,如果把 min 更新为 2,那么之前的最小值 3 就丢失了。
怎么把 3 保存起来呢?把它在 2 之前压入栈中即可。
入栈 2 ,同时将之前的 min 值 3 入栈,再把 2 入栈,同时更新 min = 2
| 2 | min = 2
| 3 |
| 5 |
|_3_|
stack
入栈 6
| 6 | min = 2
| 2 |
| 3 |
| 5 |
|_3_|
stack
出栈 6
| 2 | min = 2
| 3 |
| 5 |
|_3_|
stack
出栈 2
| 2 | min = 2
| 3 |
| 5 |
|_3_|
stack
上边的最后一个状态,当出栈元素是最小元素我们该如何处理呢?
我们只需要把 2 出栈,然后再出栈一次,把 3 赋值给 min 即可。
出栈 2
| | min = 3
| 5 |
|_3_|
stack
通过上边的方式,我们就只需要一个栈了。当有更小的值来的时候,我们只需要把之前的最小值入栈,当前更小的值再入栈即可。当这个最小值要出栈的时候,下一个值便是之前的最小值了。
class MinStack {
private Stack<Integer> stack=new Stack<>();
private int min = Integer.MAX_VALUE;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
if(x<=min)
{
stack.push(min);
min=x;
}
stack.push(x);
}
public void pop() {
if(min==stack.pop())
{
min=stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
Slayer_Zhao 发布了143 篇原创文章 · 获赞 31 · 访问量 2万+ 私信 关注