c++中如何实现栈的最小值功能_c++栈最小值实现方法-C++-PHP中文网

c++中如何实现栈的最小值功能_c++栈最小值实现方法

穿越時空

发布： 2025-10-04 11:32:02

原创

462人浏览过

用辅助栈实现最小值栈，主栈存元素，辅助栈同步存每步最小值，push时压入较小值，pop时同步弹出，确保O(1)时间完成所有操作。

c++中如何实现栈的最小值功能_c++栈最小值实现方法

在C++中实现一个能获取栈中最小值的栈结构，核心思路是用辅助栈来同步记录每个状态下的最小值。这样可以在O(1)时间内完成push、pop和getMin操作。

设计思路

维护两个栈：主栈用于存储实际元素，辅助栈用于存储对应时刻的最小值。每次入栈时，辅助栈压入当前值与栈顶较小者；出栈时两栈同时弹出，确保状态一致。

代码实现

#include <iostream>
#include <stack>
using namespace std;

class MinStack {
private:
    stack<int> data;  // 主栈
    stack<int> min;   // 辅助栈，保存最小值

public:
    void push(int val) {
        data.push(val);
        if (min.empty() || val <= min.top()) {
            min.push(val);
        } else {
            min.push(min.top());
        }
    }

    void pop() {
        if (!data.empty()) {
            data.pop();
            min.pop();
        }
    }

    int top() {
        return data.top();
    }

    int getMin() {
        return min.top();
    }

    bool empty() {
        return data.empty();
    }
};

登录后复制

使用示例

下面是一个简单的测试用例：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

int main() {
    MinStack ms;
    ms.push(3);
    ms.push(5);
    cout << "当前最小值: " << ms.getMin() << endl; // 输出 3

    ms.push(2);
    cout << "当前最小值: " << ms.getMin() << endl; // 输出 2

    ms.pop();
    cout << "当前最小值: " << ms.getMin() << endl; // 输出 3

    return 0;
}

登录后复制

这种方法空间换时间，保证了所有操作都在常数时间内完成。关键是辅助栈始终与主栈同步，每一步都保留当时的最小状态。

立即学习“C++免费学习笔记（深入）”；

基本上就这些，逻辑清晰，实现稳定。

以上就是c++++中如何实现栈的最小值功能_c++栈最小值实现方法的详细内容，更多请关注php中文网其它相关文章！