# Max Stack

`Design`

Easy

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.

2. pop() -- Remove the element on top of the stack and return it.

3. top() -- Get the element on the top.

4. peekMax() -- Retrieve the maximum element in the stack.

5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

``````MaxStack stack = new MaxStack();
stack.push(5);
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5``````

Note:

1. -1e7 <= x <= 1e7

2. Number of operations won't exceed 10000.

3. The last four operations won't be called when stack is empty.

## Solution & Analysis

### Two Stack + Custom Class

Time: O(n)

Space: O(n)

``````class MaxStack {
class Element {
int val;
int max;
public Element(int val, int max) {
this.val = val;
this.max = max;
}
}

private Deque<Element> stack;
private Deque<Element> aux;

/** initialize your data structure here. */
public MaxStack() {
stack = new ArrayDeque<Element>();
aux = new ArrayDeque<Element>();
}

public void push(int x) {
int max = x;
if (!stack.isEmpty()) {
max = Math.max(x, stack.peek().max);
}

stack.push(new Element(x, max));
}

public int pop() {
if (stack.isEmpty()) {
return -1;
}
return stack.pop().val;
}

public int top() {
if (stack.isEmpty()) {
return -1;
}
return stack.peek().val;
}

public int peekMax() {
if (stack.isEmpty()) {
return -1;
}
return stack.peek().max;
}

public int popMax() {
if (stack.isEmpty()) {
return -1;
}
int max = stack.peek().max;
while (!stack.isEmpty() && stack.peek().val != max) {
aux.push(stack.pop());
}
// pop the max
if (!stack.isEmpty()) {
stack.pop();
}

while (!aux.isEmpty()) {
push(aux.pop().val);
}
return max;
}
}

/**
* 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();
*/``````

### Space Optimized - push(Element e) to reuse Element objects

Time: 81 ms, faster than 94.91%

Space: 40.3 MB, less than 100.00%

``````class MaxStack {
class Element {
int val;
int max;
public Element(int val, int max) {
this.val = val;
this.max = max;
}
}

private Deque<Element> stack;
private Deque<Element> aux;

/** initialize your data structure here. */
public MaxStack() {
stack = new ArrayDeque<Element>();
aux = new ArrayDeque<Element>();
}

public void push(int x) {
int max = x;
if (!stack.isEmpty()) {
max = Math.max(x, stack.peek().max);
}

stack.push(new Element(x, max));
}

private void push(Element e) {
int max = e.val;
if (!stack.isEmpty()) {
max = Math.max(e.val, stack.peek().max);
}
e.max = max;
stack.push(e);
}

public int pop() {
return stack.pop().val;
}

public int top() {
return stack.peek().val;
}

public int peekMax() {
return stack.peek().max;
}

public int popMax() {
int max = stack.peek().max;
while (!stack.isEmpty() && stack.peek().val != max) {
aux.push(stack.pop());
}
// pop the max
if (!stack.isEmpty()) {
stack.pop();
}

while (!aux.isEmpty()) {
push(aux.pop());
}
return max;
}
}

/**
* 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();
*/``````

### LeetCode Official - Approach #1: Two Stacks

For `peekMax`, we remember the largest value we've seen on the side. For example if we add `[2, 1, 5, 3, 9]` in stack , we'll store `[2, 2, 5, 5, 9]` in maxStack. This works seamlessly with`pop`operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.

For`popMax`, we know what the current maximum (`peekMax`) is. We can pop until we find that maximum, then push the popped elements back on the stack.

• Time Complexity: O(N) for the `popMax`operation, and O(1) for the other operations, where N is the number of operations performed.

• Space Complexity: O(N), the maximum size of the stack.

``````class MaxStack {
Stack<Integer> stack;
Stack<Integer> maxStack;

public MaxStack() {
stack = new Stack();
maxStack = new Stack();
}

public void push(int x) {
int max = maxStack.isEmpty() ? x : maxStack.peek();
maxStack.push(max > x ? max : x);
stack.push(x);
}

public int pop() {
maxStack.pop();
return stack.pop();
}

public int top() {
return stack.peek();
}

public int peekMax() {
return maxStack.peek();
}

public int popMax() {
int max = peekMax();
Stack<Integer> buffer = new Stack();
while (top() != max) buffer.push(pop());
pop();
while (!buffer.isEmpty()) push(buffer.pop());
return max;
}
}``````

### LeetCode Official - Approach #2: Double Linked List + TreeMap

Intuition

Using structures like Array or Stack will never let us`popMax`quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making`popMax`faster than O(N) time complexity.

Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in O(1) time.

We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in O(logN) time.

Algorithm

Let's store the stack as a double linked list`dll`, and store a`map`from`value`to a`List`of`Node`.

• When we`MaxStack.push(x)`, we add a node to our`dll`, and add or update our entry`map.get(x).add(node)`.

• When we`MaxStack.pop()`, we find the value`val = dll.pop()`, and remove the node from our`map`, deleting the entry if it was the last one.

• When we`MaxStack.popMax()`, we use the`map`to find the relevant node to`unlink`, and return it's value.

The above operations are more clear given that we have a working`DoubleLinkedList`class. The implementation provided uses`head`and`tail`_sentinels_to simplify the relevant`DoubleLinkedList`operations.

A Python implementation was not included for this approach because there is no analog to_TreeMap_available.

``````class MaxStack {
TreeMap<Integer, List<Node>> map;

public MaxStack() {
map = new TreeMap();
}

public void push(int x) {
if(!map.containsKey(x))
map.put(x, new ArrayList<Node>());
}

public int pop() {
int val = dll.pop();
List<Node> L = map.get(val);
L.remove(L.size() - 1);
if (L.isEmpty()) map.remove(val);
return val;
}

public int top() {
return dll.peek();
}

public int peekMax() {
return map.lastKey();
}

public int popMax() {
int max = peekMax();
List<Node> L = map.get(max);
Node node = L.remove(L.size() - 1);
if (L.isEmpty()) map.remove(max);
return max;
}
}

tail = new Node(0);
}

Node x = new Node(val);
x.next = tail;
x.prev = tail.prev;
tail.prev = tail.prev.next = x;
return x;
}

public int pop() {
}

public int peek() {
return tail.prev.val;
}

node.prev.next = node.next;
node.next.prev = node.prev;
return node;
}
}

class Node {
int val;
Node prev, next;
public Node(int v) {val = v;}
}``````

Complexity Analysis

• Time Complexity: O(logN) for all operations except`peek`which is O(1), where N is the number of operations performed. Most operations involving`TreeMap`are O(logN).

• Space Complexity: O(N), the size of the data structures used.

## Reference

https://leetcode.com/problems/max-stack/solution/

Last updated