包含min函数的栈_

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

数据范围：操作数量满足 $0 \le n \le 300 \$ ，输入的元素满足 $|val| \le 10000 \$
进阶：栈的各个操作的时间复杂度是 $O(1)\$ ，空间复杂度是 $O(n)\$

示例:

输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出: -1,2,1,-1

解析:

"PSH-1"表示将-1压入栈中，栈中元素为-1

"PSH2"表示将2压入栈中，栈中元素为2，-1

“MIN”表示获取此时栈中最小元素==>返回-1

"TOP"表示获取栈顶元素==>返回2

"POP"表示弹出栈顶元素，弹出2，栈中元素为-1

"PSH1"表示将1压入栈中，栈中元素为1，-1

"TOP"表示获取栈顶元素==>返回1

“MIN”表示获取此时栈中最小元素==>返回-1

牛客题解官

发表于 2022-04-22 12:15:29

精华题解题目主要信息：实现栈的push、pop、top、min函数访问每个函数的时间复杂度为O(1)O(1)O(1) 举一反三：学习完本题的思路你可以解决如下题目： BM42.用两个栈实现队列方法：双栈法（推荐使用）知识点：栈栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，展开全文

不是江小白

发表于 2021-07-06 21:18:50

精华题解 1. 解题思路 1.1 回顾栈的特性只在一端插入和删除数据，并且数据存在先进后出，后进先出的特性。 1.2 图解示例示例:输入: ["PSH-1","PSH2","MIN","TOP","POP& 展开全文

开车的阿Q

发表于 2021-07-18 20:51:02

精华题解描述这是一篇面对初级coder的题解。知识点：栈难度：二星题解题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数及 pop函数的时间复杂度都是 O(1) push(value): 展开全文

Maokt

发表于 2021-06-28 10:41:00

精华题解算法思想一：定义辅助栈解题思路： 1、要用两个栈，stack用于存储元素，mins用于存储最小值，每个位置的元素都有一个对应的最小值，也就是stack和mins的长度同步增加和减少；当需要得到目前栈中的最小值的时候，直接返回mins的栈顶元素即可 2、在mins栈中先添加一个最大值，因展开全文

大菠萝侦探

发表于 2021-07-01 18:55:48

精华题解描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数及 pop函数的时间复杂度都是 O(1)push(value):将value压入栈中pop():弹出栈顶元素top():获取栈顶元素min():获取栈中最小元素算法用一个栈 s 展开全文

不会做题的小菜鸡

发表于 2021-07-18 18:59:00

精华题解思路用两个栈来实现一个是普通栈，处理入栈出栈的问题另一个是最小栈，装的是普通栈中目前的最小值，随着普通栈的入栈退栈进行同时变化方法一：利用已有栈写法（c++）关键是一定要保证最小值栈在实时跟随普通栈的变化，这样维护的最小值栈的栈顶才能随时返回来题干中要求的最小值 class S 展开全文

枫叶零渡

发表于 2021-07-02 12:09:34

精华题解描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数及 pop函数的时间复杂度都是 O(1)push(value):将value压入栈中pop():弹出栈顶元素top():获取栈顶元素min():获取栈中最小元素示例:输入: 展开全文

牛客题解官

发表于 2020-05-29 15:27:56

描述这是一篇针对初学者的题解。知识点：栈难度：一星题解题目抽象：要求实现一个O(1)时间复杂度的返回最小值的栈。正常情况下，栈的push，pop操作都为O(1),但是返回最小值，需要遍历整个栈，时间复杂度为O(n)，所以这里需要空间换时间的思想。方法：使用辅助栈首先需要一个正常栈norm 展开全文

凉风起天末

发表于 2019-08-25 23:03:30

双栈法的优化：压缩还原方法一：简单的双栈法在返回栈中的min值时，如果仅仅使用一个辅助变量min，则其值可能因为min元素被出栈而失效，常规的做法是额外添加一个同步栈（min栈），以保存记录之前所有的min值，相当于是使用了n个辅助变量，所以空间复杂度是O(n)。但是，仅仅使用一两个辅助变量就真展开全文

一叶浮尘

发表于 2019-08-14 22:41:22

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。在看到这道题目的时候第一反应是要用一个最小值来保留当前栈中最小值，但是也能够很快地意识到比较麻烦的地方在于pop的时候怎么更新min值，看了别人的题解之后都是使用了另外一个栈来保持在入栈过程中展开全文

Janebook2019

发表于 2019-08-14 20:06:34

Java实现参考了别人的思路，这里也是使用了两个栈。一个用来存所有的元素“stackTotal”,另一个用来存加入新的元素后当前stackTotal中对应的最小值。两个栈中的元素数量始终保持一致，当新的元素小于“stackLittle”栈顶元素时，“stackLittle”像栈顶push新来的元素，展开全文

郭家兴0624

发表于 2019-08-10 19:01:02

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。主流思路是应用于一个辅助栈，也就是最小元素栈。每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出展开全文

生来逆旅单行道

发表于 2021-07-11 08:56:34

本人感觉牛客官方题解的代码和细节处理的思路略显冗余（个人观点，如有错误，请指正）方法依旧是辅助栈。sta_1存放的是正常存取的一个栈，可以返会正确的top的值sta_2 维护的是一个目前最小值的栈。细节处理思路：当调用 push、pop、top 时毫无疑问，sta_1执行对应的操作，所以后面的详细展开全文

牛客82035003号

发表于 2022-03-26 21:35:27

static int stack[301]; static int i = 0; static int min_num = 99999; //假设的最小值，其实比栈中所有数都大，为的就是给机会找出展开全文

牛客882602551号

发表于 2019-12-22 13:44:32

思路：栈stack保存数据，辅助栈assist保存依次入栈最小的数 stack中依次入栈，6，5，8，4，3，9 assist依次入栈，6，5，4，3 每次入展开全文

橘红喝多会上火

发表于 2021-12-10 23:18:24

栈 + 动态规划 - 解决栈变化时原地获取该栈最小元素的问题想要随时取到当前栈中最小的元素，我们不妨另建一个栈，用来存放当原始栈含 n 个元素时，对应的栈中的最小元素（如下图）。可以看出，上图中的最小栈，是满足题目要求的，它总能保证我们可以原地获取当前原始栈中的最小元素（那就是最小栈栈顶的元素展开全文

牛客159477370号

发表于 2022-01-20 17:01:46

效率可能不是最高的，我直接线性写的。用的逻辑就是两个stack，然后同时push 同时pop，但是区别就是push的时候第二个stack会比较push进来的数值是否比自己小，如果是才会push，不然就会重复把自己下一层的value 再叠一层进来。这样做就算有pop，除非真的到了stack min 展开全文

包含min函数的栈

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题