实现一个支持O(1)时间获取最大值的栈 题目描述 设计一个栈，除了支持常规的 push、pop、top 操作外，还需要额外支持 getMax 操作，用于在 O(1) 时间内获取栈中的最大值。假设栈中元素为整数，且所有操作合法（例如不会对空栈执行 pop 或 getMax）。 解题思路 常规栈的 push 和 pop 操作已经是 O(1) 时间，但获取最大值需要遍历整个栈（O(n)）。为了实现 O(1) 的 getMax，我们需要在每次 push 和 pop 时动态维护当前栈的最大值信息。 核心思想 ：使用一个辅助栈（称为最大栈），与主栈同步操作，记录每个主栈状态下的最大值。 步骤详解 数据结构设计 主栈 stack ：存放实际元素。 辅助栈 maxStack ：存放当前主栈对应的最大值。 push 操作 将新元素 x 压入主栈。 比较 x 与当前 maxStack 栈顶元素（即当前最大值）： 若 maxStack 为空，直接将 x 压入 maxStack 。 否则，将 max(maxStack栈顶, x) 压入 maxStack 。 目的 ：确保 maxStack 栈顶始终是当前主栈的最大值。 pop 操作 同时弹出主栈和最大栈的栈顶元素。 目的 ：保持两个栈的同步，使 maxStack 栈顶仍对应主栈剩余部分的最大值。 top 操作 直接返回主栈的栈顶元素。 getMax 操作 直接返回最大栈的栈顶元素。 示例演示 操作序列：push(3), push(2), push(5), getMax(), pop(), getMax() 初始状态： stack = [] maxStack = [] push(3): stack = [3] maxStack = [3] （当前最大值 3） push(2): stack = [3, 2] maxStack = [3, 3] （比较 2 和 3，最大值仍为 3） push(5): stack = [3, 2, 5] maxStack = [3, 3, 5] （比较 5 和 3，最大值更新为 5） getMax(): 返回 maxStack 栈顶 5 ✅ pop(): stack = [3, 2] maxStack = [3, 3] （同步弹出） getMax(): 返回 maxStack 栈顶 3 ✅ 复杂度分析 时间复杂度：所有操作（push、pop、top、getMax）均为 O(1)。 空间复杂度：O(n)，最大栈需要额外存储 n 个值。 关键点总结 辅助栈与主栈 高度同步 ，但存储的是 历史最大值 的轨迹。 每次 push 时，通过比较确保最大栈的栈顶是当前主栈的最大值。 该方法可扩展至支持 O(1) 获取最小值（使用最小栈），或同时支持最大/最小值（使用两个辅助栈）。