• 【LeetCode热题100】--155.最小栈


    155.最小栈

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

    实现 MinStack 类:

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

    image-20231009101448266

    思路:

    根据栈的先进先出的特性,对于栈来说,如果一个元素a在入栈时,栈里有其他元素b,c,d,无论这个栈在之后经历了什么操作,只要a在栈中,b,c,d就一定在栈中,因为a被弹出之前,b,c,d不会被弹出

    因此,在操作过程中的任意一个时刻,只要栈顶的元素是a,那么我们就可以确定栈里面现在的元素一定是a,b,c,d

    可以在每个元素a入栈时把当前栈的最小值m存储起来,在这之后无论何时,如果栈顶元素是a,就可以直接返回存储的最小值m

    算法:

    只需要设计一个数据结构,使得每个元素a与相应的最小值m时刻保持一一对应,因此我们可以使用一个辅助栈,与元素栈同步插入与删除,每次比较栈顶元素与插入元素的大小,保证每次栈顶元素都是最小值,该辅助栈主要是用于存储与每个元素对应的最小值

    • 当一个元素要入栈时,取当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中
    • 当一个元素要出栈时,把辅助栈的栈顶元素也一并弹出
    • 在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中

    image-20231009102554548

    class MinStack {
        Deque<Integer> xStack;
        Deque<Integer> minStack;
    
        public MinStack() {
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }
        
        public void push(int val) {
            xStack.push(val);
            minStack.push(Math.min(minStack.peek(),val));  //取当前辅助栈的栈顶存储的最小值
        }
        
        public void pop() {
            xStack.pop();
            minStack.pop();
        }
        
        public int top() {
            return xStack.peek();
        }
        
        public int getMin() {
            return minStack.peek();
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
  • 相关阅读:
    Hibernate 的 Session 缓存相关操作
    C#教程9:C#方法(Methods)
    react native使用TS实现路由
    OA项目之会议通知(查询&是否参会&反馈详情)
    IP核之RAM实验
    「SpringBoot」07 指标监控
    【946. 验证栈序列】
    Vue学习笔记 —— 使用Vue的ref实现动态添加活动类名
    人大女王金融硕士项目——比努力更重要的,是要学会做对的选择
    Go 并发编程
  • 原文地址:https://blog.csdn.net/qq_46656857/article/details/133696225