### 特殊栈的设计与实现 为了设计一个能够在 \(O(1)\) 时间复杂度下完成 `push`、`pop` 和 `getMax` 操作的栈，可以采用辅助数据结构来存储当前的最大值。具体来说，在每次执行 `push` 或 `pop` 操作时更新这个辅助结构。 以下是详细的 Python 实现： #### 设计思路 通过维护两个栈： 1. **主栈 (`main_stack`)**：用于存储实际压入的数据。 2. **辅助栈 (`max_stack`)**：用于记录每一步操作后的最大值。 当向主栈中压入新元素时，如果该元素大于等于当前辅助栈顶部的值，则也将其压入辅助栈；反之则重复压入辅助栈顶部的值。这样能够确保辅助栈始终反映对应位置上的最大值[^1]。 同理，在弹出元素时同步检查并调整这两个栈的状态即可保持一致性。 下面是基于上述逻辑的具体代码实现: ```python class MaxStack: def __init__(self): self.main_stack = [] # 存储所有元素 self.max_stack = [] # 辅助栈，存储每个状态下的最大值 def push(self, value): self.main_stack.append(value) if not self.max_stack or value >= self.max_stack[-1]: self.max_stack.append(value) def pop(self): if not self.main_stack: raise IndexError("pop from empty stack") removed_value = self.main_stack.pop() if removed_value == self.max_stack[-1]: self.max_stack.pop() def getMax(self): if not self.max_stack: raise IndexError("getMax from empty stack") return self.max_stack[-1] # 测试用例 if __name__ == "__main__": s = MaxStack() s.push(3) s.push(5) print(s.getMax()) # 输出 5 s.push(7) print(s.getMax()) # 输出 7 s.pop() # 移除 7 print(s.getMax()) # 输出 5 ``` 此方法利用双栈机制实现了所需功能，并满足题目对于时间效率的要求即均为常数级别操作\(O(1)\)[^2]。