Max Stack
FabHotels
LinkedinRRateGainThe problem
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.
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.
- -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.
cpp
class MaxStack {
public:
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();
*/java
class MaxStack {
public MaxStack() {
}
public void push(int x) {
}
public int pop() {
}
public int top() {
}
public int peekMax() {
}
public 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();
*/python
class MaxStack:
def __init__(self):
def push(self, x: int) -> None:
def pop(self) -> int:
def top(self) -> int:
def peekMax(self) -> int:
def popMax(self) -> int:
# 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()javascript
var MaxStack = function() {
};
/**
* @param {number} x
* @return {void}
*/
MaxStack.prototype.push = function(x) {
};
/**
* @return {number}
*/
MaxStack.prototype.pop = function() {
};
/**
* @return {number}
*/
MaxStack.prototype.top = function() {
};
/**
* @return {number}
*/
MaxStack.prototype.peekMax = function() {
};
/**
* @return {number}
*/
MaxStack.prototype.popMax = function() {
};
/**
* Your MaxStack object will be instantiated and called as such:
* var obj = new MaxStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.peekMax()
* var param_5 = obj.popMax()
*/csharp
public class MaxStack
{
public MaxStack()
{
}
public void Push(int x)
{
}
public int Pop()
{
}
public int Top()
{
}
public int PeekMax()
{
}
public int PopMax()
{
}
}go
type MaxStack struct {
}
func NewMaxStack() *MaxStack {
}
func (ms *MaxStack) push(x int) {
}
func (ms *MaxStack) pop() int {
}
func (ms *MaxStack) top() int {
}
func (ms *MaxStack) peekMax() int {
}
func (ms *MaxStack) popMax() int {
}Stuck? Show a way to structure it+
- 01Represent stack order with a doubly linked list so arbitrary nodes can be removed quickly.
- 02Map each value to the stack/list of its live nodes and keep values in an ordered map.
- 03Use the ordered map's greatest key for max operations and remove its most recently pushed node.
- 04Keep the doubly linked list and value map synchronized on every removal.
Reference answer
Then expect these follow-ups
How would you implement the ordered map in a language without a tree map?
Tests: implementation trade-offs
Why is a heap alone insufficient?
Tests: data-structure reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question