> For the complete documentation index, see [llms.txt](https://ryukiedev.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/30.-bao-han-min-han-shu-de-zhan-rong-yi-bei-wu-dao-de-yi-ti.md).
# 30.包含min函数的栈（容易被误导的一题）
## Hi 👋
* Wechat: RyukieW
* 📦 [技术文章归档](https://ryukiedev.gitbook.io/wiki/)
* 🐙 [Github](https://github.com/RyukieSama)
| 我的个人项目 | 扫雷Elic 无尽天梯 | 梦见账本 |
| :------------------------------------------------------------------------: | :------------------------------------------------: | :-------------------------------------------------: |
| 类型 | 游戏 | 财务 |
| [AppStore](https://apps.apple.com/cn/developer/rongqing-wang/id1264542103) | [Elic](https://apps.apple.com/cn/app/id1488204246) | [Umemi](https://apps.apple.com/cn/app/id1498426607) |
## 一、 题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 `min` 函数在该栈中，调用 `min`、`push` 及 `pop` 的时间复杂度都是 `O(1)`。
示例:
```cpp
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 题相同：
来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
## 二、 分析
本题难点在于：***调用\*\*\*\* ****`min`****、****`push`**** ****及**** ****`pop`**** ****的时间复杂度都是**** \*\*\*\*`O(1)`***
并且本题很容易走进一个误区：***以为MinStack内部是有序的***（不要问我为什么知道有这个误区😂）
既然要满足 `O(1)` 的条件，一个有序集合必定是不可能完成的。
那要不考虑一下使用一个辅助的集合？
### 2.1 Top & Min
本题的示例对我来说也很有误导性...
通过这个我以为：`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栈` 栈顶既是最小元素。
## 三、 代码
```swift
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
}
}
```
