首页 > 其他分享 >剑指Offer 30.包含min的栈

剑指Offer 30.包含min的栈

时间:2022-09-05 19:56:52浏览次数:70  
标签:元素 minStack Offer 30 最小 min 栈中 push

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

 

示例:

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

提示:

各函数的调用总次数不超过 20000 次

作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/50bp33/
来源:力扣(LeetCode)

思路:

难点:降低获取栈中最小元素的时间复杂度

方法:维护一个最小值栈

元素栈每入栈一个元素

如果其比当前最小栈栈顶元素小或者栈空

将其加入到最小栈中,按照此种思想生成非严格降序的子序列

并且最小栈的栈顶元素为元素栈中的最小元素

当弹栈 时,如果当前元素等于最小栈栈顶元素 那么俩个栈同时弹栈

调用min时直接返回最小栈 栈顶元素

标签:元素,minStack,Offer,30,最小,min,栈中,push
From: https://www.cnblogs.com/TrenmenHu/p/16659356.html

相关文章

  • 2022-08-30 day38 第一小组 王鸣赫
    目录HttpServletRequest//请求HttpServletResponse//响应路径匹配servlet加载时期常见传参有2种:GET和POST区别获取一个key对应的多个值请求转发作用域其他方法Respo......
  • Docker基础知识 (9) - 使用 Docker 部署 Nginx + PHP + MariaDB(MySQL)并配置 phpMyAdmi
    1.部署PHP   1)部署环境       IP地址(本地测试环境):192.168.0.10       操作系统:LinuxCentOS7.9           Docker版本:20.10.7......
  • 2022年MinGW-w64的安装及配置教程(傻瓜式)
    1、下载:链接:https://pan.baidu.com/s/1-JhvI-x_KqxYOdWRB2C1rg提取码:scd1--来自百度网盘超级会员V4的分享2、解压1、解压到自己想要的目录(最好不要有中文路径),并复制文......
  • papamelon 305. 求和方案 Sumsets
    https://www.papamelon.com/problem/305给你一个数N,只能用2的幂次求和组成,问总共有多少种方案.输入包含多组测试数据,输入以EOF作为结束标志.每组测试数据包含一个......
  • 20201330马榕辰第一,二章学习笔记
    第一章: 一.知识点归纳:第一章前半部分重在介绍课程和书本的基本情况,包括Unix / Linux的历史,其各种发行版,我了解到了一些基本情况。后半部分主要是 Linux的使用,Lin......
  • 20201306吴龙灿学习笔记
    一、知识点归纳:第一章:引言主要内容:第一章是本书的引子,因为本书意在让我们学会Unix以及Linux相关只是,在高级语言的基础上进一步学习创造编程平台的基本语言,让我们学会硬......
  • 20201305学习笔记1
    第一章引言总述:在第一章刚开始这本书引入了Linux系统,告诉了我们Linux系统的发展历程和它的一些运行模式,他的版本,其中最主要讲的就是unbuntuLinux版本,讲了他的一些常用......
  • 【2022-08-30】哺乳
    20:00习惯的枷锁,开始的时候轻得难以察觉,到后来却重得无法摆脱。                                ......
  • 1530 bingo 不是题解
    *2600的死活卡住出不来,想啊,很想啊(指remake21*21的方阵,每个位置有一个概率是1,求凑出来bingo的概率这种题目先考虑容斥,那就是1-凑不出bingo的概率。直接做是2^44的,我做牛......
  • mysql 报错This function has none of DETERMINISTIC解决方案
    本文章向朋友们介绍开启bin-log日志mysql报错:ThisfunctionhasnoneofDETERMINISTIC,NOSQL解决办法,创建存储过程时出错信息:ERROR1418(HY000):Thisfunctionh......