标签: 栈和队列
https://leetcode.cn/problems/min-stack
设计一个支持 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.
提示:
可以额外建立一个栈(最小值栈),栈顶表示原栈中最小值。插入一个数字时,如果该值小于新栈的栈顶值说明该数是最小值,将其同时插入原栈和最小值栈。取数时,如果原栈的值等于最小值栈的值,说明这个数是原栈中的最小值,原栈和最小值栈需要同时移除该元素。
实现:每次插入栈时,都向最小值栈插入一个原栈里所有值的最小值。
class MinStack {
Stack<Integer> s;
/**
* 辅助栈
*/
Stack<Integer> minS;
public MinStack() {
s = new Stack<>();
minS = new Stack<>();
}
public void push(int val) {
s.push(val);
// 注意这里是>=
if (minS.isEmpty() || minS.peek() >= val) {
minS.push(val);
}
}
public void pop() {
int val = s.pop();
if (!minS.isEmpty() && minS.peek() == val) {
minS.pop();
}
}
public int top() {
return s.peek();
}
public int getMin() {
return minS.isEmpty() ? 0 : minS.peek();
}
}
// Integer 与 int 比较
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/