面试题30：包含min函数的栈

从“一个min变量为什么不够”开始

先预测：依次压入3、4、2，此时一个变量currentMin等于2。弹出2后，怎样在O(1)时间知道旧最小值是3？只看剩余栈顶4不够，重新扫描又要O(n)。真正缺失的不是当前答案，而是每层历史状态。

题目要求设计一个“包含min函数的栈”，使push、pop、top和min都保持O(1)。作者的方案维护数据栈m_data和m_min。每压入一个真实值，辅助栈也压入一份“到这一层为止的最小值”；每弹出一层，两边同步撤销。

因此m_min不是只收集曾经变小的候选值，而是与m_data严格等高。对序列3、4、2、3，数据栈从底到顶是3、4、2、3，辅助栈是3、3、2、2。顶层3离开时，最小值仍是2；2再离开时，下一层快照3自动恢复。

每层保存当前最小值

把m_data从栈底到第i层的最小值称为。核心关系是：对每个有效深度i，m_min[i]等于m_data[0..i]中的最小元素。原书概念“每层保存当前最小值”说的就是这个前缀关系。

push(value)时，如果m_min为空就压入value；否则比较value和旧m_min.top()，将较小者压入。作者写的是value小于旧最小值时压value，否则复制旧最小值；相等时走else，所以相同最小值仍会作为快照再次压入。

pop()不需要比较将要离开的真实值，只要两个栈各弹一次。min()直接返回m_min.top()；top()返回m_data.top()；empty()和size()以数据栈为准。只要同步关系没有被破坏，接口观察到的永远是同一深度状态。

忠实实现作者的模板

作者把实现写在StackWithMin.h中，因为C++模板定义通常需要在实例化点可见。类型T必须可复制并支持小于比较；min返回const T引用，top同时提供可写和只读引用。

#include <cassert>
#include <cstddef>
#include <stack>
 
template <typename T>
class StackWithMin {
public:
    T& top() { return m_data.top(); }
    const T& top() const { return m_data.top(); }
 
    void push(const T& value) {
        m_data.push(value);
        if (m_min.empty() || value < m_min.top()) {
            m_min.push(value);
        } else {
            m_min.push(m_min.top());
        }
    }
 
    void pop() {
        assert(!m_data.empty() && !m_min.empty());
        m_data.pop();
        m_min.pop();
    }
 
    const T& min() const {
        assert(!m_data.empty() && !m_min.empty());
        return m_min.top();
    }
 
    bool empty() const { return m_data.empty(); }
    std::size_t size() const { return m_data.size(); }
 
private:
    std::stack<T> m_data;
    std::stack<T> m_min;
};

这里没有调用标准库min函数，而是显式使用小于判断。若value与旧最小值相等，复制旧最小值与压入value在值语义上等价；辅助栈仍增加一层。这也解释了为什么作者的pop可以无条件同步，不需要判断弹出值是否等于最小值。

源代码只在pop和min中用assert检查两个栈非空，top直接交给std::stack。assert在定义NDEBUG的发布构建中会被移除，不能作为外部输入防线；空栈top、pop或min都违反接口前提。教学复现应保留这一事实，生产接口则应明确抛异常、返回optional或把空操作定义为调用方错误。

为什么四个核心操作都是O(1)

std::stack的push、pop与top在所用底层容器满足通常契约时是摊销或规定的常数级操作。一次StackWithMin.push只做两个栈push和一次比较；pop只做两个pop；top和min各做一次top。因此“push、pop、min都是O(1)”，top也同样是O(1)。

空间代价是m_data保存n个真实元素，m_min再保存n个快照，总空间O(n)，其中辅助空间O(n)。不能说空间O(1)：虽然每次操作只增加常数个元素，但随着栈深线性增长。若T很大，复制最小值可能昂贵；可以保存共享所有权、稳定索引或使用压缩方案，但每种选择都有生命周期要求。

包括两部分：两个栈高度相等；辅助栈每层是数据栈对应前缀的最小值。只核对高度不够，因为错误值也能等高；只核对栈顶最小值也不够，因为深层快照可能已损坏，直到后续pop才暴露。

正确性证明

对操作次数归纳。初始两个栈为空，高度相等，所有有效深度上的前缀命题为空真。假设操作前不变量成立。

执行push(value)后，旧层内容不变；新数据前缀只比旧前缀多value，所以新最小值恰为value与旧最小值中较小者。算法将它压入m_min，且两个栈都增加一层，不变量继续成立。

执行pop时，两个栈删除同一深度。剩余每个深度的数据前缀和对应快照都没有改变，高度仍相等。于是非空时m_min.top()就是m_data整个有效前缀的最小值，min返回正确答案。每个更新只访问栈顶，证明同时给出常数时间界。

若最小值出现两次，例如压入2、2，辅助栈也有2、2。弹出一个2后，下一层快照仍为2。这不是额外补丁，而是前缀不变量自然推出的结果。

等长快照与压缩辅助栈

另一种正确实现只在value小于或等于当前最小时把value压入辅助栈；pop前若数据栈顶等于辅助栈顶，才同步弹出。它让辅助栈大小等于“历史低点出现次数”，在严格递增输入下只占一层，但严格递减时仍是O(n)。

压缩版必须在相等时也压入，或者在辅助项中保存计数。若使用严格小于，压入两个相同最小值后只记一份；弹出第一个时删掉唯一记录，第二个最小值仍在数据栈却无从查询。泛型T还需要相等比较，而作者等长版只依赖小于关系。

#include <cstddef>
#include <functional>
#include <stack>
#include <stdexcept>
#include <utility>
 
template <class T, class Compare = std::less<T>>
class CompressedMinStack {
    std::stack<T> data;
    std::stack<std::pair<T, std::size_t>> minima;
    Compare less;
 
public:
    void push(const T& value) {
        data.push(value);
        if (minima.empty() || less(value, minima.top().first)) {
            minima.push({value, 1});
        } else if (!less(minima.top().first, value)) {
            ++minima.top().second;
        }
    }
 
    void pop() {
        if (data.empty()) {
            throw std::underflow_error("empty stack");
        }
        const T& value = data.top();
        if (!less(value, minima.top().first) &&
            !less(minima.top().first, value) &&
            --minima.top().second == 0) {
            minima.pop();
        }
        data.pop();
    }
};

这个片段省略top、min等接口以突出计数逻辑。对昂贵对象，比较和复制仍可能抛异常；压缩不等于自动更安全。等长版的优势是状态对应简单、pop无需比较，适合原题解释与一般值类型。

工程版的异常安全与接口契约

作者push先向m_data压value，再向m_min压快照。第二次分配或复制若抛异常，数据栈已经增加而辅助栈没有增加，同步不变量被破坏。对int示例通常看不见，但泛型容器不能忽略。简单修复是先算出快照并压入m_min，再尝试压m_data；若后者失败，回滚m_min。

#include <functional>
#include <optional>
#include <stack>
 
template <class T, class Compare = std::less<T>>
class SafeMinStack {
    std::stack<T> data_;
    std::stack<T> min_;
    Compare less_;
 
public:
    void push(const T& value) {
        T snapshot =
            min_.empty() || less_(value, min_.top())
                ? value
                : min_.top();
 
        min_.push(snapshot);
        try {
            data_.push(value);
        } catch (...) {
            min_.pop();
            throw;
        }
    }
 
    bool pop() {
        if (data_.empty()) return false;
        data_.pop();
        min_.pop();
        return true;
    }
 
    const T* top() const {
        return data_.empty() ? nullptr : &data_.top();
    }
 
    const T* min() const {
        return min_.empty() ? nullptr : &min_.top();
    }
};

这提供基本的事务性：push成功则两个栈都增加，失败则都保持原高度。若m_data.push成功后某种自定义栈pop也可能抛异常，设计还需更强容器保证；标准容器适配器的pop通常不抛。

min与top返回指针或引用时，下一次修改操作可能使其失效，调用方不能长期保存。若希望稳定值语义，可以返回T副本或可选值类型，代价是复制。若T的比较器定义“更大优先”，同一结构就变成max栈；名称与比较器语义必须一致。

作者八次检查逐步验证什么

作者main只使用int。Test1压3，min为3；Test2压4，min仍为3；Test3压2，min变2；Test4再压3，min仍为2。随后Test5弹出顶层3，min还是2；Test6弹出2，历史快照恢复为3；Test7弹出4，只剩3，min仍为3；Test8压0，min变0。

八次检查覆盖“更大值不改变最小值”“更小值更新最小值”“弹出普通值不改变最小值”“弹出当前最小值恢复旧值”。它没有覆盖空栈操作，也没有压入两个相等的当前最小值；工程测试必须补上这两类。

可以把官方序列写成可重复断言，并核对size与empty：

#include <cassert>
 
void testStackWithMin() {
    StackWithMin<int> stack;
    assert(stack.empty());
 
    stack.push(3); assert(stack.min() == 3);
    stack.push(4); assert(stack.min() == 3);
    stack.push(2); assert(stack.min() == 2);
    stack.push(3); assert(stack.min() == 2);
    stack.pop();   assert(stack.min() == 2);
    stack.pop();   assert(stack.min() == 3);
    stack.pop();   assert(stack.min() == 3);
    stack.push(0); assert(stack.min() == 0);
 
    StackWithMin<int> duplicates;
    duplicates.push(2);
    duplicates.push(2);
    duplicates.pop();
    assert(duplicates.min() == 2);
    assert(duplicates.size() == 1);
}

随机状态机测试可用vector作为参考模型：push追加，pop删除末尾，top比较末尾，min用线性扫描计算。被测结构仍必须O(1)，参考模型只为小规模测试服务。每次操作后检查empty、size、top和min，能在第一次同步偏移时立即定位。

并发、数值与泛型边界

该结构不是线程安全的。两个线程交错push可能让data与min来自不同操作，即使单个std::stack没有崩溃，也会破坏组合不变量。整个复合操作必须由同一把锁保护，不能分别锁两个底层栈；查询min和top也要与写操作互斥，或返回锁保护下的副本。

浮点T需要定义NaN策略。普通小于比较对NaN两边都为false，NaN可能被当作“不更小”而沿用旧值；首个元素若为NaN，则后续正常数也无法按直觉替换。业务应拒绝NaN或提供全序比较器。字符串、时间戳和业务对象同样要明确比较字段与等价关系。

若top暴露可写T引用，调用方可以原地把数据栈顶从4改成1，却不会更新辅助栈，立刻破坏不变量。作者确实提供了非const top引用，这是教学接口的隐藏风险。更稳妥的最小栈只返回const引用；若要修改栈顶，应定义replaceTop，内部用pop加push原子更新两个栈。

与都是模板从int示例走向通用库时必须补充的契约。算法正确性只说明无异常、合法调用下的min值；工程正确性还要求失败路径不破坏状态。

本章练习

本章回顾

1. 单个currentMin无法在弹出当前最小值后恢复历史答案。
2. 作者辅助栈与数据栈等高，每层保存当前前缀最小值。
3. push压入新快照，pop同步撤销两层，min直接读辅助栈顶。
4. push、pop、top、min都是O(1)，辅助空间O(n)。
5. 相等最小值也会形成新快照，因此弹出一个后答案仍正确。
6. 压缩版需保存相等值或计数，并在pop时比较两个栈顶。
7. 发布接口不能只依赖assert，非const top还可能绕过同步维护。
8. 泛型push要考虑第二次压栈失败后的回滚与引用生命周期。

名词解释