你好，同学。欢迎来到 NOI 数据结构专题训练。

今天我们要攻克的是一个非常经典的设计类问题：最小栈。这道题不仅考查你对栈（Stack）基本操作的掌握，更重要的是考查如何通过空间换时间的策略，将原本需要 $O(N)$ 遍历才能获取的信息（最小值），优化到 $O(1)$。

一、 预备知识点

在动手前，请确保你已经掌握：

1. 栈（Stack）：后进先出（LIFO）的数据结构。
2. C++ STL std::stack：
   • push()：入栈
   • pop()：出栈
   • top()：访问栈顶
3. 辅助结构思想：为了维护某种动态属性（如最大值、最小值、当前和），通常需要开辟额外的空间来记录状态历史。

二、 NOI 竞赛题目描述

题目名称：最小栈 (Min Stack) 时间限制：1.0s 内存限制 : 256MB

【问题描述】 设计一个支持以下操作的栈，要求所有操作的时间复杂度均为 $O(1)$：

1. push(x)：将元素 $x$ 推入栈中。
2. pop()：删除栈顶的元素。
3. top()：获取栈顶元素。
4. getMin()：检索栈中的最小元素。

【输入格式】 第一行包含一个整数 $N$，表示操作总数。 接下来的 $N$ 行，每行为一个操作命令：

• push x：执行入栈。
• pop：执行出栈（题目保证此时栈不为空）。
• top：查询栈顶。
• getMin：查询最小值。

【输出格式】 对于每个 top 和 getMin 操作，输出对应的结果，每个结果占一行。

【样例输入】

7
push -2
push 0
push -3
getMin
pop
top
getMin

【样例输出】

-3
0
-2

【数据规模与约定】

• $1 \le N \le 3 \times 10^4$
• $-2^{31} \le x \le 2^{31} - 1$
• 所有 pop、top、getMin 操作均在非空栈上进行。

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，我们尝试通过“同步状态法”来思考：

1. 核心矛盾：为什么单变量 min_val 不行？

• 尝试：用一个变量 min_val 记录最小值。
• 推演：
  1. push 5 -> min=5
  2. push 3 -> min=3
  3. pop -> 此时 3 走了，剩下的最小值是多少？
• 结论：单变量无法“回溯”历史。当当前的最小值被弹出时，我们需要知道上一次的最小值是什么。

2. 方案：辅助栈（同步历史记录）

• 思路：我们不仅要存数据，还要存“当数据为这么多时，当时的最小值是多少”。
• 草稿模拟：
  • 输入：push -2, push 0, push -3
  • 数据栈 (data_st)：(-2, 0, -3)
  • 最小栈 (min_st)：
    1. 存 -2 的时候，最小值是 -2。
    2. 存 0 的时候，对比 0 和 -2，最小值依然是 -2。
    3. 存 -3 的时候，对比 -3 和 -2，最小值变成 -3。
  • 此时 min_st 状态：(-2, -2, -3)
  • 执行 pop：两个栈同时弹出。min_st 现在的栈顶是 -2，完美回到了弹出 -3 之前的最小状态！

四、 复杂度分析与时间复杂度优化建议

• 时间复杂度：
  • push：$O(1)$
  • pop：$O(1)$
  • top：$O(1)$
  • getMin：$O(1)$
  • 总结：所有操作通过辅助栈直接访问栈顶，全部达到 $O(1)$。
• 空间复杂度：$O(N)$。需要额外一个等大规模的栈来存储最小值历史。

优化建议： 在考场上，如果内存极其紧张（如只有 2MB），可以使用“差值存储法”（存储 $x - min$），但这种方法涉及复杂的溢出处理。在 256MB 的标准限制下，双栈法是最稳健、最不容易写错的方案。

五、 算法流程图（伪代码逻辑）

在流程图中，我们使用括号 () 替代特殊符号以保证渲染兼容。

graph TD
    subgraph Push_Operation
    A(开始 Push x) --> B{min_st 是否为空}
    B -- 是 --> C(将 x 压入 data_st 和 min_st)
    B -- 否 --> D(计算 x 与 min_st 栈顶的较小值)
    D --> E(将 x 压入 data_st, 较小值压入 min_st)
    E --> F(Push 结束)
    end

    subgraph Pop_Operation
    G(开始 Pop) --> H(data_st 执行 pop)
    H --> I(min_st 执行 pop)
    I --> J(Pop 结束)
    end

    subgraph GetMin_Operation
    K(开始 GetMin) --> L(返回 min_st 的栈顶元素)
    end

六、 读题关键词总结

在 NOI 竞赛读题时，看到以下关键词要迅速联想到此题型：

1. “常数时间” (Constant Time / O(1))：通常意味着不能有循环，需要预处理或利用辅助空间。
2. “检索最小值” (Retrieve Minimum)：如果伴随删除操作，单变量往往不够，需要维护一个单调结构或历史栈。
3. “设计” (Implement / Design)：考查数据结构的组合能力。

教练寄语： 最小栈是“状态同步”思想的基石。记住：如果你需要知道“过去”的信息，那就把“过去”也存进栈里。去尝试实现它吧，注意 long long 的使用，虽然本题 int 范围即可，但养成处理大数据的习惯在 NOI 中非常重要！