✅ 什么是最小栈（Min Stack）？

最小栈是一种支持常数时间内（O(1)) 获取栈中最小值的栈结构。

🔧 标准栈的限制

通常，使用普通栈只能O(n) 时间遍历才能找出最小值：

1
2
stack = [3, 4, 2, 5]
min_val = min(stack)  # O(n)

但最小栈支持：

  • push(x)：压入元素
  • pop()：移出栈顶
  • top()：查看栈顶元素
  • getMin()：O(1) 获取栈中最小值

🧠 核心思想

借助一个辅助栈来同步维护当前栈的最小值。例如：

操作 原始栈(main_stack) 最小栈(min_stack)
push(5) 5 5
push(3) 5, 3 5, 3
push(4) 5, 3, 4 5, 3, 3
pop() 5, 3 5, 3
getMin() return 3 top of min_stack

✅ Python 最小栈实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MinStack:
    def __init__(self):
        self.stack = []       # 原始栈
        self.min_stack = []   # 辅助栈：保存每一步的最小值

    def push(self, val: int) -> None:
        self.stack.append(val)
        # push 到 min_stack 中的元素始终是当前最小值
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

    def getMin(self) -> int:
        return self.min_stack[-1] if self.min_stack else None

🧰 操作说明

  • push(val)：将 val 压入主栈；同时，将新最小值压入 min_stack
  • pop()：主栈和最小栈同时弹出
  • getMin()：直接返回 min_stack 栈顶

🧮 时间复杂度

操作 时间复杂度
push() O(1)
pop() O(1)
top() O(1)
getMin() O(1)

🚀 更加节省空间的变体（不重复最小元素）

上面的方法中 min_stack 与主栈等长，因为每次都同步 push，但你也可以只在 min 发生变化时记录保存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # 只在更小值加入时才记录

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

🔸这种写法更节省空间，适用于要求内存优势的场合。

📌 典型应用场景

  • 实现含最小值查询功能的数据结构
  • 辅助解决滑动窗口、括号匹配、区间最小值等问题
  • LeetCode 原题：155. 最小栈

✅ 总结

特性 说明
支持操作 push、pop、top、getMin
时间复杂度 所有操作均为 O(1)
核心数据结构 主栈 + 最小栈
空间优化方法 只在 val <= 当前最小 时记录
当然可以！下面我们讨论一种扩展数据结构：同时支持 O(1) 查询最小值和最大值的栈，即：

✅ 双向支持的最小最大栈（MinMax Stack）

💡 需求描述

构建一个MinMax 栈，支持以下操作，且所有操作都为 O(1) 时间复杂度：

  • push(val)：将元素压入栈
  • pop()：移除栈顶
  • top()：返回栈顶元素
  • getMin()：返回当前栈中最小值
  • getMax()：返回当前栈中最大值

✅ 思路

除了维护主栈，我们再用两个辅助栈：

  • min_stack：记录每一状态下的最小值
  • max_stack：记录每一状态下的最大值

每次压栈时，同步更新 min_stack 和 max_stack。

🧠 图解（push 操作）

假设我们依次压入：[3, 2, 5, 1]

Main Stack Min Stack Max Stack
3 3 3
2 2 ← min(2,3) 3 ← max(2,3)
5 2 5
1 1 ← min(1,2) 5

✅ Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MinMaxStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
        self.max_stack = []

    def push(self, val):
        self.stack.append(val)

        if not self.min_stack:
            self.min_stack.append(val)
            self.max_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))
            self.max_stack.append(max(val, self.max_stack[-1]))

    def pop(self):
        if self.stack:
            self.stack.pop()
            self.min_stack.pop()
            self.max_stack.pop()

    def top(self):
        return self.stack[-1] if self.stack else None

    def getMin(self):
        return self.min_stack[-1] if self.min_stack else None

    def getMax(self):
        return self.max_stack[-1] if self.max_stack else None

✅ 示例用法

1
2
3
4
5
6
7
8
9
10
11
s = MinMaxStack()
s.push(4)
s.push(2)
s.push(7)

print(s.getMin())  # 2
print(s.getMax())  # 7

s.pop()
print(s.getMin())  # 2
print(s.getMax())  # 4

📊 时间 & 空间复杂度

方法 时间复杂度 空间复杂度（辅助栈）
push O(1) O(n)
pop O(1) O(1)
top O(1) O(1)
getMin O(1) O(1)
getMax O(1) O(1)

✅ 空间优化（可选）

你可以进一步优化空间：只在新值小于等于当前 min / max 时才入栈
但这样做的话 pop() 时需要判断当前值是否是 min / max，略微增加复杂度。

例如：

1
2
3
if not min_stack or val <= min_stack[-1]:
    min_stack.append(val)
# 相应地，pop 时要做 if 判断

🔁 拓展

  • 如果你还希望 getMin 和 getMax 支持在 队列中 实现（单调队列），则涉及：
    • 单调栈 / 单调队列
    • 滑动窗口（滑窗最大最小）
    • 可参考：LeetCode 239 滑动窗口最大值

✅ 总结

结构 支持操作 getMin / getMax 时间复杂度 空间复杂度
正常栈 push, pop, top ✗ O(1) O(n)
最小栈 push, pop, top, getMin ✓(min only) O(1) O(n)
最大栈 push, pop, top, getMax ✓(max only) O(1) O(n)
MinMax栈 push, pop, top, getMin, getMax ✓(both) O(1) O(n)

这种结构在许多算法面试中是高频考点。灵活掌握它将对你解决各类 “最值 + 动态结构” 类问题非常有帮助。需要我给出相关题目练习吗？