算法-最小栈-LeetCode155

题目

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

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

思路

  • 最先的思路是使用 List 作为模拟栈的容器,通过使用 index 角标记录入栈出栈的位置,每次栈元素变化重新定位最小值 min,代码提交执行9ms
  • 题解最快是使用双向链表做,看一下思路,确实快,原因在于节点按顺序存储了当前值与最小值,每次入栈出栈操后不涉及额外的定位最小值,示意 node(当前值,最小值)node(1,1)->node(2,1)->node(-1,-1)->node(-2,-2)

关键

node节点既存储当前值,又存储最小值,最小值随链表有序递减

代码

package leetcode.stack;

import java.util.ArrayList;
import java.util.List;

/**
 * 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
 * <p>
 * push(x) -- 将元素 x 推入栈中。
 * pop() -- 删除栈顶的元素。
 * top() -- 获取栈顶元素。
 * getMin() -- 检索栈中的最小元素。
 * <p>
 * 示例:
 * 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 Node {
    public Node pre;
    public Node next;
    public int value;
    public int min;
}

class MinStack2 {

    Node top = null;

    /**
     * initialize your data structure here.
     */
    public MinStack2() {

    }

    public void push(int x) {
        Node node = new Node();
        node.value = x;
        if (top == null) {
            node.min = x;
        } else {
            if (top.min < x) {
                node.min = top.min;
            } else {
                node.min = x;
            }
        }
        node.pre = top;
        top = node;
    }

    /**
     * top永远指向栈顶
     * 第一个 if 判断栈是不是已经空了,空栈就没有pre节点
     * 第二个 if 判断栈是不是已经空了,不是空栈就删除next节点,断链
     */
    public void pop() {
        if (null != top) {
            top = top.pre;
            if (null != top) {
                top.next = null;
            }
        }
    }

    public int top() {
        if (null != top) {
            return top.value;
        } else {
            return -1;
        }
    }

    public int getMin() {
        return top.min;
    }
}


public class N155_2 {
    public static void main(String[] args) {
        MinStack2 minStack = new MinStack2();
        minStack.push(2147483646);
        minStack.push(2147483646);
        minStack.push(2147483647);
        System.out.println(minStack.top());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        minStack.push(2147483647);
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
        minStack.push(-2147483648);
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
    }
}
Image placeholder
handsome_young_man
未设置
  80人点赞

没有讨论,发表一下自己的看法吧

推荐文章
算法-下一个更大元素 I-LeetCode.496

题目下一个更大的元素I给定两个没有重复元素的数组 nums1和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

算法题:三角形的最小路径和

题目来源于力扣 理论基础 动态规划 三角形的最小路径和题目描述 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。说明:如果你可以只使用O(n)的额外空间(n为三角形的

ORACLE11.2.0.4 RAC+ ASM安装方法 (操作系统CENTOS7.6)

前言网上的各种文章,尝试过后,发现有很多错漏的地方,还有很多细节没有写,或者是遇到各种报错如何处理,都没写,这里是我自己整理的安装步骤和解决报错的方法,因为有部分是从自己以前的笔记里截取的截图之类的,

重启大法失效?详述Oracle11g因JDBC bug引发异常Library Cache Lock等待处理事件

墨墨导读:在Oracle11g版本中可能出现由于JDBCbug导致sql绑定变量无法共享,过期游标过多的情况,此时如果发生大量并发业务,很有可能造成异常librarycachelock等待事件,造成数

大力再出奇迹,1024 张TPU,65536 batch size,仅76分钟训练完BERT!

大数据文摘出品作者:AndyBERT作为目前工业界中训练最耗时的应用,计算量甚至远大于机器视觉中的ImageNet训练。在BERT原论文中,JacobDevlin也是用了16台云TPU(64个TPU芯

LeetCode 刷题笔记

从AmazonOA高频题开始 总结每一道做过的题目,先总结一下思路,然后记录从中获取的新知识。题目顺序不是按照序号顺序的,而是题目在真实面试中出现的频率排序。由于之前已经做过一些了,所以那些题目暂时还

用 Rust 刷 leetcode 第二题

Problem Youaregiventwonon-emptylinkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredinre

用 Rust 刷 leetcode 第一题

problemGivenanarrayofintegers,return indices ofthetwonumberssuchthattheyadduptoaspecifictarget. Youm

用 Rust 刷 leetcode 第二题

ProblemYouaregiventwo non-empty linkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredin 

宝宝也能看懂的 leetcode 周赛 - 169 - 2

1305.AllElementsinTwoBinarySearchTreesHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第2题,也是题目列表中的第13

宝宝也能看懂的 leetcode 周赛 - 169 - 1

1304.FindNUniqueIntegersSumuptoZeroHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第1题,也是题目列表中的第1304题

宝宝也能看懂的 leetcode 周赛 - 169 - 3

1306.JumpGameIIIHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第3题,也是题目列表中的第1306题--『JumpGameIII』题目描述

宝宝也能看懂的 leetcode 周赛 - 169 - 4

1307.VerbalArithmeticPuzzleHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第4题,也是题目列表中的第1307题--『Verba

LeetCode 112. 路径总和

描述给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明:叶子节点是指没有子节点的节点。注意点:必须联通到叶节点分析从根节点开始,每当遇到一个

Leetcode上最南的是哪道题?

大家伙想要找份好工作,刷题是一道绕不过的坎,Leetcode大家都很熟悉了,很多公司面试的时候会用上面的原题,今天我们就来看看这Leetcode上的题!首先依然通过利索的爬虫获取了Leetcode官网

ie11无法显示css

ie11无法显示css解决方法如下:1、在css文件的顶部加上@charset"utf-8";2、打开注册表编辑器,找到HKEY_CLASSEC_ROOT.CSS下的ContentType,然后把这个

create-react-app兼容ie11配置

今天闲来无事折腾一下create-react-app,发现主流浏览器都没有问题。但是ie11却一直报错,真是倔强的很啊。我翻了下create-react-app的文档,从中看到了正好有对ie9、ie1

ie11下不能引入外部css怎么解决?

ie11下不能引入外部css怎么解决?问题:在IE11下使用link标签引入css时,无法正常引入,直接在页面中使用style标签没问题。原因:头文件的问题。解决方法:●删除头部的●或者,将头部改成

vue1和vue2的区别是什么?

vue1和vue2的区别模板v2每个组件只允许有一个根元素,v1允许一个组件有多个根元素生命周期函数vue1.0周期解释init组件刚刚被创建,但Data、method等属性还没被计算出来create

到2025年,全球VoIP市场将达到550亿美元

基于IP的语音传输(VoIP)是当今世界许多人和企业主现代生活中不可或缺的一部分。几十年来,该技术发展迅速,延伸出了VCaaS、CCaaS、UCaaS等。然而,即使在“VoIP”已经成为常用术语的世界

DeepFakes进化版DeepNude惊现!一键“脱衣“,火到宕机

大数据文摘出品作者:蒋宝尚、赵伟人工智能的黑暗面能有多黑?这边DeepFake带来的余震还没有被平息,本周,又一AI偏门应用爆出,一键直接“脱掉”女性的衣服!海外媒体Motherboard测试图片显然

IEEE态度转变:解除对华为评审限制

大数据文摘出品作者:周素云、魏子敏IEEE的态度发生变化。今晨,IEEE电气电子工程师学会中国官网及官方公众号同时发出声明,表示IEEE向美国商务部要求就出口管制条例在IEEE出版活动的适用性做出说明

PHP跌出前十,铁打的 Python 连续3年第一:IEEE Spectrum 2019编程语言排行榜出炉

Python势头不减,依旧第一,而且进一步拉开了与其他语言的差距。这一结果,来自IEEESpectrum2019年度编程语言排行榜。这已经是Python连续3年保持第一。在Python之下,第二交椅的

IEEE官方禁止华为参与期刊审稿,当全球最大技术学术机构向政治弯腰

大数据文摘出品作者:魏子敏、宋欣仪5月29日,作为全球最大专业技术组织之一的IEEE(电气和电子工程师协会)被曝出,在发给会员的内部邮件中禁止华为员工作为旗下期刊杂志的编辑和审稿人。今天早晨,IEEE