Leetcode #716: Max Stack
In this guide, we solve Leetcode #716 Max Stack in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element. Implement the MaxStack class: MaxStack() Initializes the stack object.
Quick Facts
- Difficulty: Hard
- Premium: Yes
- Tags: Stack, Design, Linked List, Doubly-Linked List, Ordered Set
Intuition
The problem has a natural nested or last-in-first-out structure.
A stack lets us resolve matches in the correct order as we scan.
Approach
Push items as they appear and pop when you can finalize a decision.
The stack captures the unresolved part of the input.
Steps:
- Push elements as you scan.
- Pop when a rule or match is satisfied.
- Use the stack to compute results.
Example
Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]
Explanation
MaxStack stk = new MaxStack();
stk.push(5); // [5] the top of the stack and the maximum number is 5.
stk.push(1); // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5); // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top(); // return 5, [5, 1, 5] the stack did not change.
stk.popMax(); // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top(); // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop(); // return 1, [5] the top of the stack and the max element is now 5.
stk.top(); // return 5, [5] the stack did not change.
Python Solution
class Node:
def __init__(self, val=0):
self.val = val
self.prev: Union[Node, None] = None
self.next: Union[Node, None] = None
class DoubleLinkedList:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def append(self, val) -> Node:
node = Node(val)
node.next = self.tail
node.prev = self.tail.prev
self.tail.prev = node
node.prev.next = node
return node
def remove(node) -> Node:
node.prev.next = node.next
node.next.prev = node.prev
return node
def pop(self) -> Node:
return self.remove(self.tail.prev)
def peek(self):
return self.tail.prev.val
class MaxStack:
def __init__(self):
self.stk = DoubleLinkedList()
self.sl = SortedList(key=lambda x: x.val)
def push(self, x: int) -> None:
node = self.stk.append(x)
self.sl.add(node)
def pop(self) -> int:
node = self.stk.pop()
self.sl.remove(node)
return node.val
def top(self) -> int:
return self.stk.peek()
def peekMax(self) -> int:
return self.sl[-1].val
def popMax(self) -> int:
node = self.sl.pop()
DoubleLinkedList.remove(node)
return node.val
# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()
Complexity
The time complexity is O(n). The space complexity is O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.