🚀 力扣热题 155：最小栈（详细解析）
📌 题目描述
力扣 155. 最小栈
设计一个支持
push、pop、top操作，并能在常数时间内检索最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
🎯 示例
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2]AI 代码解读
💡 解题思路
本题的核心在于：如何在 O(1) 时间复杂度内获取栈中的最小值？
✅ 方法一：辅助栈法（经典解法）
使用两个栈：
- 主栈（stack）：存放正常的数据。
- 辅助栈（minStack）：每一步都存放当前栈中的最小值。
📌 操作规则：
push(x)：将x压入主栈。如果minStack为空或x <= minStack.peek()，也将x压入minStack。pop()：如果pop出的元素等于minStack的栈顶，也要将minStack弹出。getMin()：直接返回minStack的栈顶即可，时间复杂度 O(1)。
💻 Go 实现代码
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{
stack: []int{
},
minStack: []int{
},
}
}
func (this *MinStack) Push(x int) {
this.stack = append(this.stack, x)
if len(this.minStack) == 0 || x <= this.minStack[len(this.minStack)-1] {
this.minStack = append(this.minStack, x)
}
}
func (this *MinStack) Pop() {
if this.stack[len(this.stack)-1] == this.minStack[len(this.minStack)-1] {
this.minStack = this.minStack[:len(this.minStack)-1]
}
this.stack = this.stack[:len(this.stack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack)-1]
}
AI 代码解读
⏳ 复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
push |
O(1) | O(n) |
pop |
O(1) | O(1) |
top |
O(1) | O(1) |
getMin |
O(1) | O(1) |
🧠 思路拓展
除了双栈法，还有一些其他思路：
✅ 方法二：单栈 + 差值记录法（进阶）
不再使用两个栈，而是在一个栈中记录与当前最小值的差值（但这种方式实现复杂，可读性不如双栈法，实际使用中不如前者直观）。
🔍 常见易错点总结
- pop 操作忘记同步弹出 minStack：一定要保持两个栈同步。
- x == minStack.peek() 时不入栈：要注意，当前值等于最小值也要入辅助栈。
- 边界判断：构造函数要初始化为空数组，避免 nil 操作。
