Links

30.包含min函数的栈(容易被误导的一题)

Hi 👋

我的个人项目
扫雷Elic 无尽天梯
梦见账本
类型
游戏
财务
AppStore
Elic
Umemi

一、 题目

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 minpushpop 的时间复杂度都是 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
注意:本题与主站 155 题相同:https://leetcode-cn.com/problems/min-stack/
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、 分析

本题难点在于:调用 minpushpop 的时间复杂度都是 O(1)
并且本题很容易走进一个误区:以为MinStack内部是有序的(不要问我为什么知道有这个误区😂)
既然要满足 O(1) 的条件,一个有序集合必定是不可能完成的。
那要不考虑一下使用一个辅助的集合?

2.1 Top & Min

本题的示例对我来说也很有误导性...
1
通过这个我以为:Top 是最大值,整个 MinStack 是有序的...
然后整个思路就被带偏了🙈

2.2 辅助栈

我们需要准备两个栈 A:存放所有元素 & B:辅助集合

2.3 push 入栈

每当有元素入栈,正常入 A栈
然后判断 B栈栈顶元素 是否 >= 当前入栈元素 ,如果满足条件,也将元素入 B栈
这样就保证了 B栈 的栈顶元素始终是 最小的

2.4 pop 出栈

A栈 正常出栈,同时对比一下 B栈 的栈顶,如果相等,那么 B栈 也出栈。这样来保证 B栈A栈 的同步性。

2.5 top 栈顶元素

正常返回 A栈 栈顶元素即可。

2.6 min 最小元素

B栈 栈顶既是最小元素。

三、 代码

class MinStack {
var elements: [Int] = []
var smaller: [Int] = []
init() {
}
func push(_ x: Int) {
elements.append(x)
if smaller.last == nil || smaller.last ?? 0 >= x {
smaller.append(x)
}
}
func pop() {
if elements.removeLast() == smaller.last {
smaller.removeLast()
}
}
func top() -> Int {
return elements.last ?? 0
}
func min() -> Int {
return smaller.last ?? 0
}
}
02