0155. Min Stack =============== 题目信息 -------- :题号: 0155. 最小栈 :难度: Medium :主题: 栈、设计、前缀最小值、同步状态 :原题: `LeetCode 0155 `_ :重点: 为每个栈深度保留当时的最小值,使弹栈能直接恢复历史状态,并正确处理重复最小值 题目重述 -------- 设计 ``MinStack``,支持 ``push(val)``、``pop()``、``top()``、``getMin()``。前两者遵守普通栈的后进先出; ``top`` 返回栈顶值,``getMin`` 返回当前栈内最小值。四种操作都必须为 ``O(1)``。测试保证在非空栈上调用 ``pop``、``top`` 和 ``getMin``。 自建示例 -------- .. code-block:: text push(5), push(2), push(2), push(7) getMin() -> 2 pop() 删除 7 pop() 删除一个 2 getMin() -> 2 另一个 2 仍在栈中 执行 ``push(-4), push(9)`` 后,``top()`` 返回 ``9``,``getMin()`` 返回 ``-4``;栈顶与全栈最小值是两种 不同状态。 C++ 实现 -------- .. code-block:: cpp #include #include #include class MinStackWithTwoStacks { private: std::stack values_; std::stack minimums_; public: void push(int value) { values_.push(value); if (minimums_.empty() || value <= minimums_.top()) { minimums_.push(value); } } void pop() { if (values_.top() == minimums_.top()) { minimums_.pop(); } values_.pop(); } int top() { return values_.top(); } int getMin() { return minimums_.top(); } }; class MinStack { private: std::stack> entries_; public: MinStack() = default; void push(int value) { const int minimumAfterPush = entries_.empty() ? value : std::min(value, entries_.top().second); entries_.push({value, minimumAfterPush}); } void pop() { entries_.pop(); } int top() { return entries_.top().first; } int getMin() { return entries_.top().second; } }; 题解 ---- 为什么只保存当前最小值仍然不够 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 普通栈只需保存元素,``push``、``pop``、``top`` 都访问一端。若 ``getMin`` 每次扫描全栈,最坏为 ``O(n)``; 若只额外保存一个变量 ``currentMinimum``,压入时可以常数更新,但弹出当前最小元素后,不知道它下面历史 元素的最小值,仍要重新扫描。 缺少的信息不是“现在最小值是多少”,而是“回到每个旧栈深度时最小值应恢复成什么”。栈的后进先出顺序 允许把这段历史也按栈保存。 方案一:第二个栈只记录最小值变化 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ``MinStackWithTwoStacks`` 的 ``values_`` 保存全部值,``minimums_`` 保存仍有效的最小值候选。压入值不大于 当前最小时,它成为新深度的最小值并同步压入;弹出值等于当前最小时,也同步弹出最小栈。于是 ``minimums_.top()`` 始终是全栈最小值。 条件必须是 ``value <= minimums_.top()``,不能只在严格更小时记录。连续压入两个 ``2`` 后,最小栈也应 保存两个 ``2``;弹出上面一个时,只删除一份,下面的 ``2`` 仍证明当前最小值为二。若只记录一次,第一次 弹出就会错误暴露更大的旧最小值,甚至让最小栈为空。 该方法只在最小值不增时追加辅助项,某些输入可少存状态;代价是 ``push``、``pop`` 都要保持两个栈同步, 相等分支是容易出错的地方。 方案二:每一层绑定压入后的前缀最小值 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 主实现让每个栈项保存二元组: .. code-block:: text {当前 value, 压入它之后整个栈的 minimum} 压入时,新最小值只可能是当前值或旧栈顶保存的最小值,两者取小即可。弹出时,值与这一层的最小状态一起 删除;新的栈顶已经携带上一深度的正确最小值,无需判断刚删的值是否等于最小值。 不变量与具体走读 ~~~~~~~~~~~~~~~~ ``entries_`` 中任一位置 ``i`` 的 ``second``,等于从栈底到位置 ``i`` 所有 ``first`` 的最小值。因此栈顶 二元组同时回答普通栈顶和全栈最小值。 .. list-table:: :header-rows: 1 * - 操作 - 新压入二元组 - 栈顶最小值 * - ``push(5)`` - ``(5, 5)`` - ``5`` * - ``push(2)`` - ``(2, 2)`` - ``2`` * - ``push(2)`` - ``(2, 2)`` - ``2`` * - ``push(7)`` - ``(7, 2)`` - ``2`` * - ``pop()`` 两次 - 删除 ``(7,2)``、上层 ``(2,2)`` - 下一项仍为 ``(2,2)``,最小值 ``2`` 每次压入后不变量由 ``min(value, oldMinimum)`` 成立;弹出只恢复一个此前已经正确的前缀状态,所以归纳地 覆盖任意操作序列。 为什么不使用最小堆 ~~~~~~~~~~~~~~~~~~ 最小堆能常数取得最小值,但删除的必须是栈顶最近元素,而它可能位于堆中间;需要额外身份、延迟删除或索引 维护,操作也通常达到 ``O(log n)``。这里查询只随栈深度回退,前缀最小值正好匹配后进先出的历史结构, 无需引入更通用的数据结构。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开类 ``MinStack`` 采用二元组栈。四个操作都只读取或修改栈顶,严格 ``O(1)``;每个输入元素多保存一个 整数,空间 ``O(n)``。双栈方案同样满足时间要求,并可能在最小值很少变化时少存辅助项;二元组方案选择 固定的一层一状态对应,牺牲少量常数空间换取无分支的弹出与更容易维护的不变量。