题意概括

要求设计并实现一个特殊的栈结构，除了要支持常规栈的 push (入栈)、pop (出栈) 和 top (查看栈顶) 操作外，还必须额外实现一个 getMin 方法。这个 getMin 方法需要能够在常数时间复杂度 O(1) 内，返回该栈中当前所有元素的最小值。

操作说明:

• push x: 将整数 x 压入栈。
• pop: 弹出栈顶元素。
• top: 返回栈顶元素的值。
• getMin: 返回栈中当前的最小值。

数据范围:

• 操作总数 $N$ 满足 $1 \le N \le 10^4$。
• 压入的整数 $x$ 范围为 $[-10^9, 10^9]$。

基础知识

解决本题的关键在于如何设计数据结构，使得 getMin 操作能够达到 $O(1)$ 的时间复杂度，同时不影响其他基本操作的效率。常规的栈在查找最小值时需要遍历所有元素，复杂度为 $O(N)$，不符合题意。

辅助栈法 (Auxiliary Stack):

这是实现“最小栈”最经典和直观的方法。我们使用两个栈协同工作：

1. 数据栈 (Data Stack): 一个普通的栈，用来存储所有被压入的元素。我们称之为 stk。
2. 辅助栈 (Minimum Stack): 另一个栈，我们称之为 mstk。这个栈的特殊之处在于，它的栈顶元素永远是当前数据栈 stk 中所有元素的最小值。它是一个单调不增的栈。

操作逻辑实现:

• push x 操作:

  1. 将元素 x 正常压入数据栈 stk。
  2. 检查辅助栈 mstk：
     • 如果 mstk 为空，或者新元素 x 小于或等于 mstk 的栈顶元素，那么就将 x 也压入 mstk。
     • (使用“小于等于”是为了正确处理多个相同最小值的情况。当一个最小值被弹出后，如果栈中还有与之相等的元素，mstk 依然能正确指向它。)

• pop 操作:

  1. 首先，查看即将从 stk 弹出的元素 stk.top()。
  2. 如果这个元素恰好与 mstk 的栈顶元素相等，说明当前栈中的最小值即将被移除。因此，mstk 也需要弹出其栈顶元素，以确保 mstk 的新栈顶是 stk 剩余元素中的最小值。
  3. 最后，将 stk 的栈顶元素弹出。

• top 操作: 直接返回 stk 的栈顶元素 stk.top()。

• getMin 操作: 由于 mstk 的栈顶始终保存着当前最小值，所以直接返回 mstk.top() 即可。这是一个 $O(1)$ 操作。

复杂度分析:

• 所有操作 (push, pop, top, getMin) 的时间复杂度均为 $O(1)$。
• 空间复杂度为 $O(N)$。在最坏情况下（例如，压入的元素序列是严格递减的），辅助栈 mstk 需要存储所有 N 个元素。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    int n;
    // 使用 long long 防止整数溢出
    stack<ll> stk, mstk; 

    cin >> n;
    for (int i = 0; i < n; ++i) {
        string op;
        cin >> op;

        if (op == "push") {
            ll x;
            cin >> x;
            stk.push(x);
            // 关键：当辅助栈为空或x小于等于其栈顶时，x入辅助栈
            if (mstk.empty() || x <= mstk.top()) {
                mstk.push(x);
            }
        } else if (op == "pop") {
            // 如果弹出的元素是当前最小值，辅助栈也要弹出
            if (stk.top() == mstk.top()) {
                mstk.pop();
            }
            stk.pop();
        } else if (op == "top") {
            cout << stk.top() << endl;
        } else if (op == "getMin") {
            cout << mstk.top() << endl;
        }
    }
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    // 如果是严格的多组，可以用 while(cin >> n) { ... }
    slv();

    return 0;
}

/*
样例输入 1:
8
push -2
push 0
push -3
getMin
pop
top
getMin

样例输出 1:
-3
0
-2

样例输入 2:
5
push 5
push 3
getMin
push 1
getMin

样例输出 2:
3
1
*/