实现一个支持O(1)时间获取最大值的栈

题目描述
设计一个栈，除了支持常规的入栈（push）、出栈（pop）操作外，还需要支持在O(1)时间内获取栈中的最大值。

解题思路
常规栈的push和pop操作都是O(1)时间，但获取最大值需要遍历整个栈，时间复杂度为O(n)。为了实现O(1)时间获取最大值，我们可以使用一个辅助栈来同步记录每个状态下的最大值。

具体实现步骤

1. 数据结构设计

   • 使用两个栈：
     • dataStack：存储实际数据的主栈
     • maxStack：存储当前最大值的辅助栈，栈顶始终对应主栈当前状态的最大值

2. push操作实现

   • 将新元素压入dataStack
   • 比较新元素与maxStack栈顶元素的大小：
     • 如果maxStack为空，直接将新元素压入maxStack
     • 否则，将新元素与maxStack栈顶元素中的较大值压入maxStack
   • 时间复杂度：O(1)

3. pop操作实现

   • 同时弹出dataStack和maxStack的栈顶元素
   • 返回dataStack弹出的元素
   • 时间复杂度：O(1)

4. getMax操作实现

   • 直接返回maxStack的栈顶元素（不弹出）
   • 时间复杂度：O(1)

完整代码示例（Java）

class MaxStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> maxStack;

    public MaxStack() {
        dataStack = new Stack<>();
        maxStack = new Stack<>();
    }
    
    public void push(int x) {
        dataStack.push(x);
        if (maxStack.isEmpty()) {
            maxStack.push(x);
        } else {
            maxStack.push(Math.max(x, maxStack.peek()));
        }
    }
    
    public int pop() {
        maxStack.pop();
        return dataStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMax() {
        return maxStack.peek();
    }
}

示例演示
操作序列：push(3), push(5), push(2), getMax(), pop(), getMax()

执行过程：

1. push(3)

   • dataStack: [3]
   • maxStack: [3]（当前最大值3）

2. push(5)

   • dataStack: [3,5]
   • maxStack: [3,5]（比较5和3，取较大值5）

3. push(2)

   • dataStack: [3,5,2]
   • maxStack: [3,5,5]（比较2和5，取较大值5）

4. getMax() → 返回5（maxStack栈顶）

5. pop()

   • dataStack弹出2 → [3,5]
   • maxStack弹出5 → [3,5]
   • 返回2

6. getMax() → 返回5（maxStack栈顶）

复杂度分析

• 时间复杂度：所有操作都是O(1)
• 空间复杂度：O(n)，辅助栈需要额外空间

关键点说明

• 辅助栈与主栈保持同步操作（同进同出）
• 辅助栈的大小始终与主栈保持一致
• 每次push时，辅助栈存入的是当前主栈所有元素中的最大值
• 这种设计确保了任何时候都能直接获取当前栈的最大值