Min Stack

1. 问题描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack.

Example:

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

2. 求解

主要是模拟写一个最小栈。要注意push时可能会输入null。需要使用双栈实现,一个保存数据,一个保存最小值。由于随着数据出栈,最小值是不断变化的,因此需要一个最小值栈来保存最小值。

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        if(minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
        stack.push(x);
    }

    public void pop() {
        if(stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();        
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 54. Spiral Matrix

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • matplotlib的基本用法(四)——设置legend图例

    本文主要是关于matplotlib的一些基本用法。 Demo import matplotlib.pyplot as plt import numpy as n...

    Tyan
  • 求1000000以内的素数

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • (含源码)「自然语言处理(NLP)」Question Answering(QA)论文整理(二)

    本次整理的论文主要偏向于Open-Domain QA,共8篇文章,其中主要涉及到混合注意力方法、预训练模型分析、BERT预训练模型优化、QA数据集、问答跳转等...

    ShuYini
  • 逆风而行!从考研失败到收获到自己满意的Offer,分享一下自己的经历!

    大家好,我是Guide哥,这篇文章是一位读者的投稿。这篇文章分享了他从确定Java后端方向 -> 考研 -> 考研失败->准备春招 -> 收货自己满意的offe...

    Guide哥
  • 如何利用图形基元?

    WolframChina
  • 起底小程序数据分析,每一个指标都不应该被忽视

    你可能做了一个小程序,也做了很多推广。 然后查看了后台的一些数据: 有本地也有外地; 有男粉丝也有女粉丝; 有青年才俊,也有中年大叔; 有iPhone也有安卓;...

    企鹅号小编
  • 支付渠道那些事

    从这一篇开始,进入重构工作的正题了。 在支付系统中,支付网关和支付渠道的对接是最核心的功能。其中支付网关是对外提供服务的接口,所有需要渠道支持的资金操作都需要通...

    用户1499526
  • 支付流程的坑点

    3.同一订单重复提交数据或者是重复请求,在微信获取时已经申请预付单的订单再次发起请求。

    用户1499526
  • 在Chrome中截取整个网页

    经常使用谷歌浏览器的话,如果要想对网页截图,大多都直接使用系统自带截屏方式或者第三方截屏。但如果要把网页整个截取下来的话,你可以试试Chrome自带的截屏功能。...

    Inkedus

扫码关注云+社区

领取腾讯云代金券