C++实现常数时间复杂度获取最小值的栈

需求分析与设计目标

设计一个栈结构，需支持以下四种基础操作，且要求检索最小元素的操作必须在常数时间 $O(1)$ 内完成：

• push(x)：将元素 x 推入栈中。
• pop()：删除栈顶的元素。
• top()：获取栈顶元素。
• getMin()：检索栈中的最小元素。

若使用单一标准栈，在执行 getMin() 时需遍历整个栈寻找最小值，其时间复杂度为 $O(n)$，无法满足题目对常数时间复杂度的严格要求。因此，我们需要一种空间换时间的策略。

第1步：理解双栈协作原理

为了实现 $O(1)$ 的 getMin() 操作，我们可以维护两个栈：

1. 数据栈（datastack）：用于按顺序存储所有入栈的元素，保证正常的 push、pop 和 top 功能。
2. 最小值栈（sortedstack）：专门用于记录数据栈在任何时刻的最小值。该栈的栈顶始终保存着当前数据栈中的最小元素。

在 push 操作中，当新元素进入数据栈的同时，我们判断它是否小于或等于当前最小值栈的栈顶元素。如果是，则将其也压入最小值栈；否则不操作，因为当前最小值未变。

第2步：构建C++类接口

基于上述逻辑，我们在C++中使用 std::stack 容器实现该类。以下是完整的头文件及方法实现代码：

```cpp
class MinStack {
public:
    /** initialize your data structure here. */
    //创建两个栈
    stack<int> datastack; //数据栈，存储所有输入值
    stack<int> sortedstack; //有序栈（最小值栈），栈底最大，栈顶最小，只有当新元素 <= 栈顶时才push
    
    MinStack() {
        // 初始化函数，无需额外操作
    }
    
    void push(int val) {
        datastack.push(val); //将值push到数据栈
        // 判断是否需要更新最小值栈
        //当有序栈为空 或 新值小于等于有序栈的栈顶元素 就push
        if(sortedstack.empty()||val<=sortedstack.top()) {
            sortedstack.push(val);
        }
    }
    
    void pop() {
        //关键点：只有当数据栈出栈的元素恰好也是当前最小值时，才需要从最小值栈中弹出对应元素
        if(!datastack.empty() && datastack.top()==sortedstack.top()) {  
            sortedstack.pop();
        }
        datastack.pop();  //数据栈一直在出栈
    }         
    
    int top() {
        return datastack.top();
    }
    
    int getMin() {
        return sortedstack.top();
    }
};
/**
 * Your MinStack object will be instantiated and called such that:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
```

第3步：验证执行流程

以 LeetCode 经典测试用例为例，验证上述逻辑的正确性：

• 输入指令：["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
  
• 参数列表：[[], [-2], [0], [-3], [], [], [], []]
  
• 详细执行过程：
  
  1. new MinStack()：初始化两个空栈。
  2. push(-2)：数据栈[-2]，最小值栈[-2]。返回 -2（默认无输出）。
  3. push(0)：数据栈[-2, 0]。因 0 >= -2，最小值栈保持不变 [-2]。返回 0（默认无输出）。
  4. push(-3)：数据栈[-2, 0, -3]。因 -3 < -2，最小值栈变为 [-2, -3]。返回 -3（默认无输出）。
  5. getMin()：直接读取最小值栈栈顶，结果返回 -3。
  6. pop()：移除数据栈顶 -3。同时数据栈顶(-3) == 最小值栈顶(-3)，故最小值栈移除栈顶，变为 [-2]。正常移除数据栈。
  7. top()：读取数据栈当前栈顶，结果返回 0。
  8. getMin()：读取最小值栈当前栈顶，结果返回 -2。
• 预期输出：[null,null,null,null,-3,null,0,-2]
  

此流程证明了双栈机制在处理动态变化的最小值时的高效性与准确性。

总结

通过使用一个主数据栈配合一个最小值辅助栈，我们成功地将“查询最小值”的时间复杂度从 $O(n)$ 降低到了 $O(1)$。虽然这引入了额外的空间开销，但在大多数实时系统或高频操作场景中，这种空间换时间的做法是极具性价比的经典设计。以上就是用C++实现常数时间最小栈的详细内容，更多关于C++数据结构设计与优化的资料请关注本站其它相关文章！