如何在Python中实现一个支持O(1)获取最小值的栈-Python教程-PHP中文网

单靠list.append()无法满足o(1)取最小值，因为list不维护最小值信息，min()为o(n)，且仅缓存self._min无法在pop时o(1)还原上一最小值。

如何在python中实现一个支持o(1)获取最小值的栈

为什么单靠list.append()无法满足O(1)取最小值

Python 的 list 本身没有维护最小值信息，每次调用 min() 都是 O(n)；即使缓存一个 self._min 变量，弹出时也无法在 O(1) 内还原上一个最小值——因为栈是后进先出，历史最小值可能已被覆盖或丢弃。

用辅助栈同步记录最小值的正确姿势

核心思路：用另一个栈 self._min_stack 跟踪每个状态下的最小值。入栈时，如果新元素 ≤ 当前最小值（即 _min_stack[-1]），就把它也压入辅助栈；出栈时，若主栈弹出的是当前最小值，辅助栈也同步弹出。

关键细节：

_min_stack 初始应推入一个极大值（如 float('inf')）或留空，但判空逻辑必须统一
比较必须用 而非 <code>，否则重复最小值（如 <code>[3,1,1,4]）会导致辅助栈少存一个 1，get_min() 在第二次 pop() 后失效
所有操作（push、pop、get_min）都严格 O(1)，空间最坏 O(n)，但这是必要代价

示例片段：

python全能编程助手

SkillSub Pro - Python 题解与代码注释双功能技能功能概述SkillSub Pro - Python 题解与代码注释双功能技能是一项面向实际任务的技能，主要用于SkillSub Pro 是一个 Python 题解生成与代码注释的双功能合体技能，专为学生、算法学习者和开发者设计；✅ 一个技能，两种用途：；核心要点📝 题解模式：输入题目/题号，自动生成完整 Python 题解（含详细注释、解题思路、复杂度分析）；💬 注释模式：输入 Python 代码，自动添加详细中。它将相关步骤、

下载

class MinStack:
    def __init__(self):
        self._stack = []
        self._min_stack = [float('inf')]  # 哨兵，避免判空
<pre class="brush:python;toolbar:false;">def push(self, x: int) -> None:
    self._stack.append(x)
    if x <= self._min_stack[-1]:
        self._min_stack.append(x)

def pop(self) -> None:
    if self._stack.pop() == self._min_stack[-1]:
        self._min_stack.pop()

def get_min(self) -> int:
    return self._min_stack[-1]