LeetCode hot100-70

最新推荐文章于 2025-06-02 14:28:44 发布

alike_meng

最新推荐文章于 2025-06-02 14:28:44 发布

阅读量230

点赞数 3

分类专栏： leetcode 文章标签： leetcode 算法职场和发展

本文链接：https://blog.csdn.net/alike_meng/article/details/144460552

版权

leetcode 专栏收录该内容

100 篇文章

订阅专栏

https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked

155. 最小栈
已解答
中等
相关标签
相关企业
提示
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

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

这题主要目的是实现一个O(1)就能得到最小元素的一个栈。普通的栈无法做到这点。官方解法是用的两个双端队列来实现的。

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(val,minStack.peek()));
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.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();
 */