【LeetCode】最小栈

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

  • push(x) -- 将元素 x 推入栈中。
  • pop() -- 删除栈顶的元素。
  • top() -- 获取栈顶元素。
  • getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.


由于栈先进后出的特点,希望用最高效率取最小值,那么意味着要消耗空间,我们需要有个空间来记录最小值在目标值,这样就可以满足要求,实现最小值

class MinStack {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        s1.push(x);
        if (s2.isEmpty() || s2.peek() >= x) s2.push(x);//s2始终存着s1栈内的最小值
    }
    
    public void pop() {
        int x = s1.pop();
        if (s2.peek() == x) s2.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨熹的专栏

什么是条件随机场 CRF: Conditional Random Fields

Conditional Random Fields 条件随机场,是一种判别模型,可以用于预测序列数据,通过使用过去的上下文信息,使模型达到更好的预测效果。

55230
来自专栏五分钟学算法

图解LeetCode第 26 号问题:删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

26630
来自专栏五分钟学算法

【图解数据结构】 一组动画彻底理解选择排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

11620
来自专栏编程一生

不够聪明所以选择工程?

曾经听一个面试者说过:因为觉得自己不够聪明所以选择了工程,如果自己足够聪明的话就去做算法了。对于他这段话我思考的很久,最后的结论是:Are you kiddin...

8810
来自专栏五分钟学算法

冰与火之歌:「时间」与「空间」复杂度

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和...

12910
来自专栏Java架构沉思录

面试重灾区之原子操作你有必要了解下

在JDK1.5+的版本中,Doug Lea和他的团队还为我们提供了一套用于保证线程安全的原子操作。我们都知道在多线程环境下,对于更新对象中的某个属性、更新基本类...

13520
来自专栏五分钟学算法

看动画轻松理解「链表」实现「LRU缓存淘汰算法」

前几节学习了「链表」、「时间与空间复杂度」的概念,本节将结合「循环链表」、「双向链表」与 「用空间换时间的设计思想」来设计一个很有意思的缓存淘汰策略:LRU缓存...

14320
来自专栏linux驱动个人学习

LRU算法

内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。

42420
来自专栏量子位

AlphaZero登上《科学》封面:一个算法“通杀”三大棋,完整论文首次发布

不仅会下围棋,还自学成才横扫国际象棋和日本将棋的DeepMind AlphaZero,登上了最新一期《科学》杂志封面。

8020
来自专栏五分钟学算法

看动画轻松理解时间复杂度(二)

上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级,这篇文章来讲讲另外几种复杂度: 递归算法的时间复杂度(recursive algorithm ...

10540

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励