目录

我们直接看题解吧:

题目:

解题方法:

难度分析:

审题目+事例+提示:

解题分析:

解题思路:

代码实现:

代码补充说明:  


题目地址

155. 最小栈 – 力扣(LeetCode)

难度简单

今天刷最小栈,大家有兴趣可以点上看看题目要求,试着做一下

我们直接看题解吧:

题目:

设计一个支持 pushpoptop 操作,并能在常数时间检索到最小元素的栈。

实现 MinStack 类:

   MinStack() 初始化堆栈对象
   void push(int val) 将元素val推入堆栈
   void pop() 删除堆栈顶部的元素。
   int top() 获取堆栈顶部的元素。
   int getMin() 获取堆栈中的最小元素。

解题方法

方法1、辅助栈

方法2、差值法

难度分析

主要考察如何常数时间内返回最小值

审题目+事例+提示

常数时间内检索到最小值

解题分析

实现方法中其他pop ,push,top等方法均能在常数时间内实现,但getmin()方法只利用现有的栈的话,则需要进行线性扫描整个栈来获得最小值,即无法在常数时间内实现题目要求,因此我们现有栈的基础上可以另外定义一个辅助栈,其栈顶元素保存最小值,与元素栈同步插入删除

解题思路

1、当一个元素要入栈时,我们当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中;

2、当一个元素要出栈时,我们把辅助栈的栈顶元素也一并弹出

3、在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中

代码实现

class MinStack {
    Deque<Integer&gt; xStack;   //注意,Deque一个接口
    Deque<Integer&gt; minStack; //定义双端Deque双端队列作为元素栈与辅助栈

    public MinStack() {
        xStack = new LinkedList<Integer&gt;();      //在构造方法创建双向链表集合对象
        minStack = new LinkedList<Integer&gt;();   //利用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一个双端队列接口继承自Queue接口

    · Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque,其中LinkedList是最常用的。

    ·Deque堆栈操作方法:push()、pop()、peek()等。

 

原文地址:https://blog.csdn.net/m0_70437378/article/details/134748261

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_33106.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注