剑指 Offer 30 - 包含 min 函数的栈
# 📃 题目描述
题目链接:
# 🔔 解题思路
用两个栈,一个栈 stack1 存元素,一个栈 stack2 存 stack1 中当前状态的最小值
- 当一个元素 x 要入栈时,我们取当前 stack2 的栈顶存储的最小值,与当前元素 x 比较得出最小值,将这个最小值插入辅助栈中;
- 当一个元素要出栈时,我们把 stack2 的栈顶元素也一并弹出
- 在任意一个时刻,栈内元素的最小值就存储在 stack2 的栈顶元素中
class MinStack {
// 存储元素
private Stack<Integer> stack;
// 存储最小值
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
}
else {
minStack.push(Math.min(minStack.peek(), x));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
/**
* 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.min();
*/
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10