Max Stack
Design
Easy
Design a max stack that supports push, pop, top, peekMax and popMax.
push(x) -- Push element x onto stack.
pop() -- Remove the element on top of the stack and return it.
top() -- Get the element on the top.
peekMax() -- Retrieve the maximum element in the stack.
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:
-1e7 <= x <= 1e7
Number of operations won't exceed 10000.
The last four operations won't be called when stack is empty.
Solution & Analysis
Two Stack + Custom Class
主要思想:用Element这个custom class,存入val以及当前max。这样只需在push时比较栈顶就能得到当前max。
唯一的难点在popMax(),因为只需要pop max值对应的元素,因此需要辅助stack来存pop出来的元素,当pop 完 max 元素之后,再将辅助stack中元素push回原来的stack即可,但是这是要用MaxStack class本身的push(int x),因为需要更新此时stack中的max。此外可以进一步优化push(),再创建一个push(Element e),这样就可以不用每次stack.push时都new一下Element。
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 withpop
operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.
ForpopMax
, 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 uspopMax
quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of makingpopMax
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 listdll
, and store amap
fromvalue
to aList
ofNode
.
When we
MaxStack.push(x)
, we add a node to ourdll
, and add or update our entrymap.get(x).add(node)
.When we
MaxStack.pop()
, we find the valueval = dll.pop()
, and remove the node from ourmap
, deleting the entry if it was the last one.When we
MaxStack.popMax()
, we use themap
to find the relevant node tounlink
, and return it's value.
The above operations are more clear given that we have a workingDoubleLinkedList
class. The implementation provided useshead
andtail
_sentinels_to simplify the relevantDoubleLinkedList
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;
DoubleLinkedList dll;
public MaxStack() {
map = new TreeMap();
dll = new DoubleLinkedList();
}
public void push(int x) {
Node node = dll.add(x);
if(!map.containsKey(x))
map.put(x, new ArrayList<Node>());
map.get(x).add(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);
dll.unlink(node);
if (L.isEmpty()) map.remove(max);
return max;
}
}
class DoubleLinkedList {
Node head, tail;
public DoubleLinkedList() {
head = new Node(0);
tail = new Node(0);
head.next = tail;
tail.prev = head;
}
public Node add(int val) {
Node x = new Node(val);
x.next = tail;
x.prev = tail.prev;
tail.prev = tail.prev.next = x;
return x;
}
public int pop() {
return unlink(tail.prev).val;
}
public int peek() {
return tail.prev.val;
}
public Node unlink(Node node) {
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 involvingTreeMap
are O(logN).Space Complexity: O(N), the size of the data structures used.
Reference
Last updated
Was this helpful?