LeetCode 0716. Max Stack Solution in Java, C++ & Python | Explanation + Code

Description

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.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

 

Example 1:

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.

 

Constraints:

• -107 <= x <= 107
• At most 105 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Solutions

Solution 1

PythonJavaC++

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 @staticmethod 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()(code-box)

class Node { public int val; public Node prev, next; public Node() { } public Node(int val) { this.val = val; } } class DoubleLinkedList { private final Node head = new Node(); private final Node tail = new Node(); public DoubleLinkedList() { head.next = tail; tail.prev = head; } public Node append(int val) { Node node = new Node(val); node.next = tail; node.prev = tail.prev; tail.prev = node; node.prev.next = node; return node; } public static Node remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; return node; } public Node pop() { return remove(tail.prev); } public int peek() { return tail.prev.val; } } class MaxStack { private DoubleLinkedList stk = new DoubleLinkedList(); private TreeMap<Integer, List<Node>> tm = new TreeMap<>(); public MaxStack() { } public void push(int x) { Node node = stk.append(x); tm.computeIfAbsent(x, k -> new ArrayList<>()).add(node); } public int pop() { Node node = stk.pop(); List<Node> nodes = tm.get(node.val); int x = nodes.remove(nodes.size() - 1).val; if (nodes.isEmpty()) { tm.remove(node.val); } return x; } public int top() { return stk.peek(); } public int peekMax() { return tm.lastKey(); } public int popMax() { int x = peekMax(); List<Node> nodes = tm.get(x); Node node = nodes.remove(nodes.size() - 1); if (nodes.isEmpty()) { tm.remove(x); } DoubleLinkedList.remove(node); return x; } } /** * Your MaxStack object will be instantiated and called as such: * MaxStack obj = new MaxStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.peekMax(); * int param_5 = obj.popMax(); */(code-box)

class MaxStack { public: MaxStack() { } void push(int x) { stk.push_back(x); tm.insert({x, --stk.end()}); } int pop() { auto it = --stk.end(); int ans = *it; auto mit = --tm.upper_bound(ans); tm.erase(mit); stk.erase(it); return ans; } int top() { return stk.back(); } int peekMax() { return tm.rbegin()->first; } int popMax() { auto mit = --tm.end(); auto it = mit->second; int ans = *it; tm.erase(mit); stk.erase(it); return ans; } private: multimap<int, list<int>::iterator> tm; list<int> stk; }; /** * Your MaxStack object will be instantiated and called as such: * MaxStack* obj = new MaxStack(); * obj->push(x); * int param_2 = obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->peekMax(); * int param_5 = obj->popMax(); */(code-box)