最小栈(155)题解
最小 题解 155
2023-06-13 09:14:29 时间
题目
分析
此题中的push
、pop
、top
操作都是Stack
及Deque
等类可以支持的,它们的时间复杂度为O(1)
。难点在于getMain
方法,获取堆栈中的最小元素,如果遍历整个堆栈区找寻最小值时间复杂度为O(n)
,想要将时间复杂度优化到O(1)
就需要辅助栈。
push操作:
辅助栈跟原始栈的操作是一致的,但是辅助栈的数据需要取push
值跟当前辅助栈值的最小值
,这样在获取栈内最小值时直接从辅助栈进行peek
获取栈顶数据即可。
辅助栈的步骤跟原始栈的步骤一致,push
跟pop
都同步入栈
跟出栈
,要达到两个栈操作的一致。pop
操作就简单了,不需要判断直接两个栈进行pop
即可,就不画图了,看下面代码。
代码
辅助栈初始化时需要写入一个最大值,否则第一次比对栈顶没有内容会报错。
class MinStack {
ArrayDeque<Integer> stack;
ArrayDeque<Integer> minStack;
public MinStack() {
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(minStack.peek(), val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
相关文章
- 已知最大公约数和最小公倍数_7和15的最大公因数和最小公倍数
- 【C语言】4种方法求最大公约数和最小公倍数及比较它们的运行时间
- AIC(最小信息化准则)
- 【最小表示法】模板级运用的“困难”题
- 每个开发人员都要掌握的:最小 Linux 基础课
- 记一次centos最小安装
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
- 大羊驼LLaMa竞品来了:AI画图最火公司开源语言模型,最小30亿参数
- 机器学习之线性回归的最小二乘法求解详解大数据
- 最小查询MySQL表中ID的最大最小值(mysqlid最大)
- 化Oracle最小化:更好的数据处理(oracle最小)
- Oracle特性:最大致胜,最小不失。(oracle最大最小)
- Redis缓存中的精确之笔精确到最小单位(redis缓存的最小单位)