Max Stack - Leetcode Solution

The Max Stack problem on LeetCode tasks you with implementing a data structure that supports basic stack operations (push, pop, peek) as well as finding the maximum element in the stack.

One approach to solving this problem is to use two stacks: one to store the values in the stack, and another to keep track of the maximum elements seen so far.

When a new element is pushed onto the stack, it is added to the value stack as usual. If it is greater than or equal to the current maximum (found at the top of the max stack), it is also added to the max stack.

When an element is popped from the stack, it is removed from both the value and max stacks if it is the current maximum. This ensures that the max stack always stores the maximum element in the stack.

To find the maximum element in the stack, simply return the top element of the max stack.

Here is an implementation of this approach in Python:

class MaxStack:
    def __init__(self):
        self.val_stack = []
        self.max_stack = []

    def push(self, x: int) -> None:
        self.val_stack.append(x)
        if not self.max_stack or x >= self.max_stack[-1]:
            self.max_stack.append(x)

    def pop(self) -> int:
        if self.val_stack[-1] == self.max_stack[-1]:
            self.max_stack.pop()  # remove from max stack if it's the current max
        return self.val_stack.pop()

    def top(self) -> int:
        return self.val_stack[-1]

    def peekMax(self) -> int:
        return self.max_stack[-1]

    def popMax(self) -> int:
        max_val = self.max_stack.pop()  # remove from max stack
        buffer = []
        while self.val_stack[-1] != max_val:
            buffer.append(self.pop())  # pop values until we find the max
        self.pop()  # remove the max value from the val stack
        for val in reversed(buffer):
            self.push(val)  # push the other values back onto the stack
        return max_val

The popMax method is slightly more complicated. It first pops the maximum value from the max stack. Then, it pops values from the value stack until it finds the maximum value. These values are stored in a buffer stack. The maximum value is then removed from the value stack, and the values from the buffer stack are pushed back onto the value stack in reverse order.

This implementation has a time complexity of O(n) for the popMax method in the worst case where all values in the stack are equal and we need to pop them all. All other operations have a time complexity of O(1).

1