30.包含min函数的栈(容易被误导的一题)
Last updated
Last updated
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min
函数在该栈中,调用 min
、push
及 pop
的时间复杂度都是 O(1)
。
示例:
提示:
各函数的调用总次数不超过 20000
次
注意:本题与主站 155 题相同:https://leetcode-cn.com/problems/min-stack/
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
本题难点在于:调用 min
、push
及 pop
的时间复杂度都是 O(1)
并且本题很容易走进一个误区:以为MinStack内部是有序的(不要问我为什么知道有这个误区😂)
既然要满足 O(1)
的条件,一个有序集合必定是不可能完成的。
那要不考虑一下使用一个辅助的集合?
本题的示例对我来说也很有误导性...
通过这个我以为:Top
是最大值,整个 MinStack
是有序的...
然后整个思路就被带偏了🙈
我们需要准备两个栈 A:存放所有元素
& B:辅助集合
。
每当有元素入栈,正常入 A栈
。
然后判断 B栈
的 栈顶元素
是否 >= 当前入栈元素
,如果满足条件,也将元素入 B栈
。
这样就保证了 B栈
的栈顶元素始终是 最小的
。
A栈
正常出栈,同时对比一下 B栈
的栈顶,如果相等,那么 B栈
也出栈。这样来保证 B栈
与 A栈
的同步性。
正常返回 A栈
栈顶元素即可。
B栈
栈顶既是最小元素。
我的个人项目
扫雷Elic 无尽天梯
梦见账本
类型
游戏
财务