在栈的各种操作中，我们通常需要push（入栈）、pop（出栈）、top（获取栈顶元素）这些基本功能。但如果要快速获取栈中的最小元素呢？如果每次都遍历整个栈来找最小值，效率就太低了。今天就来教你一个妙招——用双栈法实现一个支持O(1)时间复杂度查询最小值的栈，轻松应对面试中的这类问题！

问题：普通栈的痛点

普通的栈结构虽然能高效完成入栈、出栈操作，但要获取栈中的最小元素却很麻烦。比如有一个栈，元素依次为[3, 2, 4, 1, 5]，要找到最小值1，只能从头到尾遍历一遍，时间复杂度是O(n)。如果需要频繁查询最小值，这种方法显然不够高效。

题目要求我们设计一个栈，除了支持push、pop、top操作外，还能通过min函数在O(1)时间内返回当前栈中的最小元素。

核心思路：双栈协作，各司其职

解决这个问题的关键是引入辅助栈。我们需要两个栈：

• 数据栈（Data）：负责存储所有元素，实现基本的push、pop、top操作。
• 辅助栈（Min）：专门记录对应数据栈状态下的最小值，让min函数可以直接取栈顶元素。

具体操作规则如下：

1. 入栈（push）时：
2. 直接将元素压入数据栈。
3. 对于辅助栈：
4. 如果辅助栈为空，直接将当前元素压入。
5. 如果辅助栈不为空，比较当前元素与辅助栈顶元素：
6. 若当前元素更小，就将其压入辅助栈。
7. 若当前元素更大或相等，就将辅助栈顶元素再次压入（保证辅助栈与数据栈长度一致，方便后续操作）。
8. 出栈（pop）时：
9. 数据栈和辅助栈同时弹出栈顶元素（因为两者长度始终一致）。
10. 获取栈顶元素（top）时：
11. 直接返回数据栈的栈顶元素。
12. 获取最小值（min）时：
13. 直接返回辅助栈的栈顶元素（因为辅助栈顶始终记录当前最小值）。

举个例子，一目了然

我们用一个具体的入栈过程来演示： 假设依次入栈的元素为：3 → 2 → 4 → 1 → 5

• 入栈3：
• 数据栈：[3]
• 辅助栈为空，压入3 → [3]
• 当前min为3
• 入栈2：
• 数据栈：[3, 2]
• 2 < 辅助栈顶3，压入2 → [3, 2]
• 当前min为2
• 入栈4：
• 数据栈：[3, 2, 4]
• 4 > 辅助栈顶2，压入2 → [3, 2, 2]
• 当前min仍为2
• 入栈1：
• 数据栈：[3, 2, 4, 1]
• 1 < 辅助栈顶2，压入1 → [3, 2, 2, 1]
• 当前min为1
• 入栈5：
• 数据栈：[3, 2, 4, 1, 5]
• 5 > 辅助栈顶1，压入1 → [3, 2, 2, 1, 1]
• 当前min仍为1

此时如果执行pop操作（弹出5）：

• 数据栈变为：[3, 2, 4, 1]
• 辅助栈变为：[3, 2, 2, 1]
• min仍为1（辅助栈顶）

再执行pop操作（弹出1）：

• 数据栈变为：[3, 2, 4]
• 辅助栈变为：[3, 2, 2]
• min变为2（辅助栈顶）

通过这个例子可以清晰地看到，辅助栈始终同步记录着数据栈对应的最小值，实现了O(1)时间查询。

代码实现：C++和Python版本

C++版本

#include <stack>
using namespace std;

class Solution {
public:
    // 入栈操作
    void push(int value) {
        // 数据栈直接压入元素
        Data.push(value);
        // 辅助栈处理：空栈直接压入，否则压入较小值
        if (Min.empty()) {
            Min.push(value);
        } else {
            // 若当前值更小则压入当前值，否则压入原最小值（保持栈顶为当前最小值）
            int min_val = Min.top() < value ? Min.top() : value;
            Min.push(min_val);
        }
    }
    
    // 出栈操作
    void pop() {
        // 数据栈和辅助栈同时弹出
        if (!Data.empty()) {
            Data.pop();
            Min.pop();
        }
    }
    
    // 获取栈顶元素
    int top() {
        return Data.top();
    }
    
    // 获取最小值
    int min() {
        return Min.top();
    }

private:
    stack<int> Data;  // 数据栈：存储所有元素
    stack<int> Min;   // 辅助栈：存储对应状态的最小值
};

Python版本

class Solution:
    def __init__(self):
        # 初始化数据栈和辅助栈
        self.Data = []  # 存储所有元素
        self.Min = []   # 存储对应状态的最小值

    def push(self, node):
        """入栈操作"""
        self.Data.append(node)
        if self.Min:
            # 辅助栈非空时，压入当前最小值（原最小值与新元素的较小者）
            if self.Min[-1] > node:
                self.Min.append(node)
            else:
                self.Min.append(self.Min[-1])
        else:
            # 辅助栈为空时，直接压入当前元素
            self.Min.append(node)

    def pop(self):
        """出栈操作"""
        if not self.Data:
            return None
        # 数据栈和辅助栈同时弹出栈顶元素
        self.Min.pop()
        return self.Data.pop()

    def top(self):
        """获取栈顶元素"""
        if not self.Data:
            return None
        return self.Data[-1]

    def min(self):
        """获取当前最小值"""
        if not self.Min:
            return None
        return self.Min[-1]

为什么这种方法高效？

• 时间复杂度：push、pop、top、min四个操作的时间复杂度都是O(1)，因为每个操作都只涉及栈的顶部元素，没有遍历或其他耗时操作。
• 空间复杂度：O(n)，需要额外的辅助栈存储最小值，最坏情况下（元素单调递增），辅助栈与数据栈存储相同元素，空间翻倍。但相比时间效率的提升，这种空间开销通常是可接受的。

总结

带min函数的栈是面试中的经典问题，核心思路是用双栈协作：数据栈负责存储元素，辅助栈同步记录对应状态的最小值。这种方法既保证了所有操作的高效性，又易于理解和实现。

掌握了这个技巧，不仅能轻松解决这类问题，还能加深对栈结构和空间换时间思想的理解。下次面试遇到类似问题，就再也不怕啦！