Implement a Stack That Supports O(1) Time Retrieval of Maximum Value

Problem Description
Design a stack that supports standard push and pop operations, and also supports retrieving the maximum value in the stack in O(1) time.

Solution Approach
Standard stack operations push and pop are O(1), but retrieving the maximum value requires traversing the entire stack, which has a time complexity of O(n). To achieve O(1) time retrieval of the maximum value, we can use an auxiliary stack to synchronously record the maximum value for each state.

Detailed Implementation Steps

1. Data Structure Design

   • Use two stacks:
     • dataStack: The main stack storing the actual data.
     • maxStack: An auxiliary stack storing the current maximum value. Its top always corresponds to the maximum value in the current state of the main stack.

2. Implementation of Push Operation

   • Push the new element onto dataStack.
   • Compare the new element with the top element of maxStack:
     • If maxStack is empty, directly push the new element onto maxStack.
     • Otherwise, push the larger value between the new element and the top element of maxStack onto maxStack.
   • Time Complexity: O(1)

3. Implementation of Pop Operation

   • Pop the top elements from both dataStack and maxStack simultaneously.
   • Return the element popped from dataStack.
   • Time Complexity: O(1)

4. Implementation of getMax Operation

   • Directly return the top element of maxStack (without popping it).
   • Time Complexity: O(1)

Complete Code Example (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();
    }
}

Example Walkthrough
Operation sequence: push(3), push(5), push(2), getMax(), pop(), getMax()

Execution process:

1. push(3)

   • dataStack: [3]
   • maxStack: [3] (current maximum: 3)

2. push(5)

   • dataStack: [3,5]
   • maxStack: [3,5] (compare 5 and 3, take the larger value 5)

3. push(2)

   • dataStack: [3,5,2]
   • maxStack: [3,5,5] (compare 2 and 5, take the larger value 5)

4. getMax() → returns 5 (top of maxStack)

5. pop()

   • dataStack pops 2 → [3,5]
   • maxStack pops 5 → [3,5]
   • returns 2

6. getMax() → returns 5 (top of maxStack)

Complexity Analysis

• Time Complexity: All operations are O(1).
• Space Complexity: O(n), as the auxiliary stack requires extra space.

Key Points

• The auxiliary stack operates synchronously with the main stack (push and pop together).
• The size of the auxiliary stack always matches that of the main stack.
• Each push operation stores the maximum value of all current elements in the main stack into the auxiliary stack.
• This design ensures that the current maximum value of the stack can always be retrieved directly at any time.