实现带有最小值功能的栈

问题描述：设计一种栈结构，除了常规的栈操作外，还需要提供一个能够快速获取栈内最小元素的方法。

解决方案：

template 
class MinStack {
public:
    void push(T value) {
        mainStack.push(value);
        if (minStack.empty() || value <= minStack.top()) {
            minStack.push(value);
        }
    }

    void pop() {
        if (mainStack.top() == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
    }

    T top() const {
        return mainStack.top();
    }

    T min() const {
        return minStack.top();
    }

private:
    std::stack mainStack; // 主栈
    std::stack minStack;  // 辅助栈，用于存储最小值
};

原理分析：

此问题的关键在于如何在不影响栈的基本特性（后进先出）的前提下，高效地维护一个最小值。最直接的想法是在每次插入新元素时对栈进行排序，但这会破坏栈的结构特性，并且时间复杂度过高。另一种方法是为每个元素维护一个额外的最小值信息，但这种方法在元素被移除时难以维护最小值的正确性。

最优解是使用一个辅助栈来跟踪最小值。每当向主栈中添加一个新元素时，如果该元素小于或等于当前辅助栈的顶部元素，则也将其添加到辅助栈中。这样，辅助栈的顶部始终代表主栈中的最小值。当从主栈中移除元素时，如果该元素也是当前最小值，则同步从辅助栈中移除，以保持辅助栈的正确性。

这种方法确保了所有操作的时间复杂度均为O(1)，并且不会改变栈的基本特性。

示例：

假设执行以下操作序列：

• push(3)


• push(5)


• min() -> 返回 3


• push(2)


• push(1)


• min() -> 返回 1


• pop()


• min() -> 返回 2


• pop()


• min() -> 返回 3

在这个过程中，辅助栈帮助我们有效地追踪了最小值的变化。