本文介绍: 题目:设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
我们直接看题解吧:
题目:
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
解题方法:
方法1、辅助栈
难度分析:
审题目+事例+提示:
解题分析:
在实现方法中其他pop ,push,top等方法均能在常数时间内实现,但getmin()方法只利用现有的栈的话,则需要进行线性扫描整个栈来获得最小值,即无法在常数时间内实现题目要求,因此我们现有栈的基础上可以另外定义一个辅助栈,其栈顶元素保存最小值,与元素栈同步插入与删除。
解题思路:
代码实现:
class MinStack {
Deque<Integer> xStack; //注意,Deque是一个接口
Deque<Integer> minStack; //定义双端Deque双端队列作为元素栈与辅助栈
public MinStack() {
xStack = new LinkedList<Integer>(); //在构造方法中创建双向链表集合对象
minStack = new LinkedList<Integer>(); //利用Deque接口其中的一个实现类
minStack.push(Integer.MAX_VALUE); //初始化压入一个int整型最大值,MAX_VALUE
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x)); //比较当前值与之前最小值
}
public void pop() {
xStack.pop(); //同步弹出栈元素
minStack.pop();
}
public int top() {
return xStack.peek(); //返回元素栈顶元素
}
public int getMin() {
return minStack.peek(); //返回辅助栈的元素
}
}
。
代码补充说明:
注意哈:
Java堆栈Stack类已经过时,Java官方推荐使用Deque替代Stack使用。
· Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque,其中LinkedList是最常用的。
原文地址:https://blog.csdn.net/m0_70437378/article/details/134748261
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_33106.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。