Solution For Max Stack
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).
Step by Step Implementation For Max Stack
class MaxStack {
Stack stack;
Stack maxStack;
/** initialize your data structure here. */
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 buffer = new Stack<>();
while (top() != max) buffer.push(pop());
pop();
while (!buffer.isEmpty()) push(buffer.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();
*/ class MaxStack:
def __init__(self):
self.stack = []
self.max_stack = []
def push(self, val):
self.stack.append(val)
# compare val with the current max, and update max_stack accordingly
if not self.max_stack or val >= self.max_stack[-1]:
self.max_stack.append(val)
def pop(self):
# pop both stack and max_stack
val = self.stack.pop()
if val == self.max_stack[-1]:
self.max_stack.pop()
return val
def max(self):
return self.max_stack[-1]/**
* @param {number} x
* @return {number}
*/
var maxStack = function() {
this.stack = [];
this.max = [];
};
/**
* @param {number} x
* @return {void}
*/
maxStack.prototype.push = function(x) {
this.stack.push(x);
if (this.max.length === 0 || x >= this.max[this.max.length - 1]) {
this.max.push(x);
}
};
/**
* @return {number}
*/
maxStack.prototype.pop = function() {
const val = this.stack.pop();
if (val === this.max[this.max.length - 1]) {
this.max.pop();
}
return val;
};
/**
* @return {number}
*/
maxStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
/**
* @return {number}
*/
maxStack.prototype.peekMax = function() {
return this.max[this.max.length - 1];
};
/**
* @param {number} x
* @return {void}
*/
maxStack.prototype.popMax = function() {
const idx = this.stack.indexOf(this.max[this.max.length - 1]);
this.stack.splice(idx, 1);
this.max.pop();
};class MaxStack {
public:
/** initialize your data structure here. */
MaxStack() {
}
void push(int x) {
}
int pop() {
}
int top() {
}
int peekMax() {
}
int popMax() {
}
};
/**
* 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();
*/public class MaxStack {
Stack stack;
Stack maxStack;
/** initialize your data structure here. */
public MaxStack() {
stack = new Stack();
maxStack = new Stack();
}
public void Push(int x) {
stack.Push(x);
if(maxStack.Count == 0 || x >= maxStack.Peek()) {
maxStack.Push(x);
}
}
public int Pop() {
int val = stack.Pop();
if(val == maxStack.Peek()) {
maxStack.Pop();
}
return val;
}
public int Top() {
return stack.Peek();
}
public int PeekMax() {
return maxStack.Peek();
}
public int PopMax() {
int max = maxStack.Peek();
Stack temp = new Stack();
while(Top() != max) {
temp.Push(Pop());
}
Pop();
while(temp.Count > 0) {
Push(temp.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();
*/