首页 > 包含min函数的栈
开通博客写题解
头像 牛客题解官
发表于 2022-04-22 12:15:29
题目主要信息： 实现栈的push、pop、top、min函数 访问每个函数的时间复杂度为O(1)O(1)O(1) 举一反三： 学习完本题的思路你可以解决如下题目： BM42.用两个栈实现队列 方法：双栈法（推荐使用） 知识点：栈 栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶， 展开全文
去ta的博客 赞 (35) 回复(5) 收起
头像 不是江小白
发表于 2021-07-06 21:18:50
1. 解题思路 1.1 回顾栈的特性 只在一端 插入和删除数据，并且数据存在先进后出，后进先出的特性。 1.2 图解示例 示例:输入: ["PSH-1","PSH2","MIN","TOP","POP& 展开全文
去ta的博客 赞 (32) 回复(2) 收起
头像 开车的阿Q
发表于 2021-07-18 20:51:02
描述 这是一篇面对初级coder的题解。 知识点：栈 难度：二星 题解 题目： 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1) push(value): 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 Maokt
发表于 2021-06-28 10:41:00
算法思想一：定义辅助栈 解题思路： 1、要用两个栈，stack用于存储元素，mins用于存储最小值，每个位置的元素都有一个对应的最小值，也就是stack和mins的长度同步增加和减少；当需要得到目前栈中的最小值的时候，直接返回mins的栈顶元素即可 2、在mins栈中先添加一个最大值，因 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 枫叶零渡
发表于 2021-07-02 12:09:34
描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)push(value):将value压入栈中pop():弹出栈顶元素top():获取栈顶元素min():获取栈中最小元素示例:输入: 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 大菠萝侦探
发表于 2021-07-01 18:55:48
描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)push(value):将value压入栈中pop():弹出栈顶元素top():获取栈顶元素min():获取栈中最小元素 算法 用一个栈 s 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 不会做题的小菜鸡
发表于 2021-07-18 18:59:00
思路 用两个栈来实现 一个是普通栈，处理入栈出栈的问题 另一个是最小栈，装的是普通栈中目前的最小值，随着普通栈的入栈退栈进行同时变化 方法一：利用已有栈写法（c++） 关键是一定要保证最小值栈在实时跟随普通栈的变化，这样维护的最小值栈的栈顶才能随时返回来题干中要求的最小值 class S 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客题解官
发表于 2020-05-29 15:27:56
描述 这是一篇针对初学者的题解。知识点：栈难度：一星 题解 题目抽象：要求实现一个O(1)时间复杂度的返回最小值的栈。正常情况下，栈的push，pop操作都为O(1),但是返回最小值，需要遍历整个栈，时间复杂度为O(n)，所以这里需要空间换时间的思想。 方法：使用辅助栈 首先需要一个正常栈norm 展开全文
去ta的博客 赞 (106) 回复(9) 收起
头像 凉风起天末
发表于 2019-08-25 23:03:30
双栈法的优化：压缩还原 方法一：简单的双栈法在返回栈中的min值时，如果仅仅使用一个辅助变量min，则其值可能因为min元素被出栈而失效，常规的做法是额外添加一个同步栈（min栈），以保存记录之前所有的min值，相当于是使用了n个辅助变量，所以空间复杂度是O(n)。 但是，仅仅使用一两个辅助变量就真 展开全文
去ta的博客 赞 (69) 回复(9) 收起
头像 一叶浮尘
发表于 2019-08-14 22:41:22
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 在看到这道题目的时候第一反应是要用一个最小值来保留当前栈中最小值，但是也能够很快地意识到比较麻烦的地方在于pop的时候怎么更新min值，看了别人的题解之后都是使用了另外一个栈来保持在入栈过程中 展开全文
去ta的博客 赞 (37) 回复(9) 收起
头像 Janebook2019
发表于 2019-08-14 20:06:34
Java实现参考了别人的思路，这里也是使用了两个栈。一个用来存所有的元素“stackTotal”,另一个用来存加入新的元素后当前stackTotal中对应的最小值。两个栈中的元素数量始终保持一致，当新的元素小于“stackLittle”栈顶元素时，“stackLittle”像栈顶push新来的元素， 展开全文
去ta的博客 赞 (35) 回复(2) 收起
头像 郭家兴0624
发表于 2019-08-10 19:01:02
题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 主流思路是应用于一个辅助栈，也就是最小元素栈。 每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出 展开全文
去ta的博客 赞 (12) 回复(0) 收起
头像 生来逆旅单行道
发表于 2021-07-11 08:56:34
本人感觉牛客官方题解的代码和细节处理的思路略显冗余（个人观点，如有错误，请指正）方法依旧是辅助栈。sta_1存放的是正常存取的一个栈，可以返会正确的top的值sta_2 维护的是一个目前最小值的栈。细节处理思路：当调用 push、pop、top 时 毫无疑问，sta_1执行对应的操作，所以后面的详细 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 牛客82035003号
发表于 2022-03-26 21:35:27
static int stack[301]; static int i = 0; static int min_num = 99999; //假设的最小值，其实比栈中所有数都大，为的就是给机会找出 展开全文
去ta的博客 赞 (9) 回复(1) 收起
头像 牛客882602551号
发表于 2019-12-22 13:44:32
思路：栈stack保存数据，辅助栈assist保存依次入栈最小的数        stack中依次入栈，6，5，8，4，3，9           assist依次入栈，6，5，4，3 每次入 展开全文
去ta的博客 赞 (6) 回复(4) 收起
头像 橘红喝多会上火
发表于 2021-12-10 23:18:24
栈 + 动态规划 - 解决栈变化时原地获取该栈最小元素的问题 想要随时取到当前栈中最小的元素，我们不妨另建一个栈，用来存放当原始栈含 n 个元素时，对应的栈中的最小元素（如下图）。 可以看出，上图中的最小栈，是满足题目要求的，它总能保证我们可以原地获取当前原始栈中的最小元素（那就是最小栈栈顶的元素 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 每天学习一点
发表于 2022-02-13 01:52:16
（1）辅助栈方法 使用两个栈维护数据，一个作为普通栈，一个保存历史最小值 public class Solution { //正常栈操作 private Stack<Integer> stack = new Stack<Integer>(); //保 展开全文
去ta的博客 赞 (4) 回复(1) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”