![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/723fd41a42614bbc9b976bd9edc97da3.png)
![[头条]笔试题——最小栈](https://www.bmabk.com/wp-content/uploads/2022/05/post-loading.gif)
![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/1196938b101147f3b27a898655f460fc.png)
解法一：（相对解法二，会非常鸡肋）
思路：
- 由于获取堆栈最小元素时间复杂度为O(1)，所有用创建一个变量min用来存放最小值
- 将存放最小值的变量min设为Integer.MAX_VALUE
- push方法里，每push一次用min比较
- 创建两个栈，第一个栈用来存放数据，第二栈用来通过变量第一个栈而得出最小数据的零时栈
class MinStack {
public Stack<Integer> stack;
public Stack<Integer> stackTmp;
public MinStack() {
stack = new Stack<>();
stackTmp = new Stack<>();
}
//先赋最大值
public int min = Integer.MAX_VALUE;
public void push(int val) {
//有比他小的就赋值
if(val < min){
min = val;
}
stack.push(val);
}
public void pop() {
if(stack.pop() == min){
//被pop后min需要重新赋值，依旧用最大值
min = Integer.MAX_VALUE;
//将所有元素转移到stackTmp，目的是为了让min重新与所有元素比较
while(!stack.empty()){
int tmp = stack.pop();
if(tmp < min){
min = tmp;
}
stackTmp.push(tmp);
}
//再转移到stack
while(!stackTmp.empty()){
stack.push(stackTmp.pop());
}
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}解法二：（分析如下）
![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/90513709f88648f59ce6574a86f0f3a8.png)
![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/29b9e3639a73443f9a94a6d307dff66f.png)
![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/83e51dbe0aeb45fd819cb51f0cfadee2.png)
![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/a9d5487552e74d409b80c91c714be9d5.png)
![[头条]笔试题——最小栈](https://img-blog.csdnimg.cn/f54e0a5cfab64112ae40b52d4f59a73f.png)
代码如下：
class MinStack {
Stack<Integer> stack;//普通栈
Stack<Integer> stackMin;//最小栈
public MinStack() {
stack = new Stack<>();
stackMin = new Stack<>();
}
//压栈
public void push(int val) {
//给最小站赋初值
if(stackMin.empty()){
stackMin.push(val);
}
//若不是初值，先判断是否小于等于（等于是以防pop后为空）最小栈栈顶元素，若是，才给最小栈压栈
else if(stackMin.peek() >= val){
stackMin.push(val);
}
stack.push(val);
}
public void pop() {
if((int)stackMin.peek() == (int)stack.peek()){
stackMin.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return stackMin.peek();
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/124358.html
