首页 > 试题广场 >

最小栈

[编程题]最小栈
  • 热度指数：5633 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
实现一个最小栈，有三种操作，min：得到栈中的最小值，push：在栈顶插入一个元素，pop：弹出栈顶元素，使这三种操作的时间复杂度都是O(1)
要求：语言不限

输入描述:
第一行是一个数Q，接下来Q行每行表示一个操作，每行首先是操作op
若op==0,则输出当前栈中的最小值；
若op==1，表示push，接着正整数x，把在x放进栈顶；
若op==2，表示pop，弹出栈顶元素
保证Q<=500000,保证op==0或2时（即min操作和pop操作时）栈不为空。
你可以假设一开始栈的空的。


输出描述:
对应每个op==0或2，如果是op==0输出当前栈中的最小值，如果是op==2输出弹出的元素。
示例1

输入

7
1 3
1 4
0
1 2
0
2
0

输出

3
2
2
3

说明

第一个操作为push 3,此时栈元素为3
第二个操作为push 4,此时栈元素为3,4
第三个操作为min,此时栈元素为3,4，输出最小值3
第四个操作为push 2,此时栈元素为3,4,2
第五个操作为min,此时栈元素为3,4,2，输出最小值2
第六个操作为pop,弹出元素2，此时栈元素为3,4，输出弹出的元素2
第七个操作为min,此时栈元素为3,4，输出最小值3
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 18:51:57
题解： 考察点： 栈 易错点： 本题要求、、三种操作都在复杂度内完成，也就是说都必须在常数时间内完成，其中和都是栈本来的操作，很多同学会考虑使用堆来维护最小值，但是这是不对的，因为堆每次找最小值的时间复杂度为 题解： 可以考虑使用两个栈来共同维护，一个栈用来进行元素常规的出栈和入栈操作，另一个栈维护 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客第一菜狗
发表于 2021-05-22 01:35:03
可以不使用线性的额外空间，只需要O(1)的额外空间复杂度：· 记录minx，表示当前最小值。push(x)时，判断x是否大于minx。· 使用栈s，push的不是原始插入值，而是差值：x-minx。 若x>=minx，则皆大欢喜，直接push(x-minx)，不需要修改minx。对应的pop 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 Momenta 模拟 栈 2019 Java工程师
来自：Momenta2019...
上传者：小小
难度：
23条回答 7981浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最小栈

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号