Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.void push(int val)
pushes the elementval
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.
Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output[null,null,null,null,-3,null,0,-2]
Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Constraints:
-231 <= val <= 231 - 1
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks. - At most
3 * 104
calls will be made topush
,pop
,top
, andgetMin
.
Min Stack Solutions
✅Time: O(1)
✅Space: O(n)
C++
class MinStack {
public:
void push(int x) {
if (stack.empty())
stack.emplace(x, x);
else
stack.emplace(x, min(x, stack.top().second));
}
void pop() {
stack.pop();
}
int top() {
return stack.top().first;
}
int getMin() {
return stack.top().second;
}
private:
stack<pair<int, int>> stack; // {x, min}
};
Java
class MinStack {
public void push(int x) {
if (stack.isEmpty())
stack.push(new int[] {x, x});
else
stack.push(new int[] {x, Math.min(x, stack.peek()[1])});
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
private Stack<int[]> stack = new Stack<>(); // {x, min}
}
Python
class MinStack:
def __init__(self):
self.stack = []
def push(self, x: int) -> None:
mini = x if not self.stack else min(self.stack[-1][1], x)
self.stack.append([x, mini])
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
Watch Tutorial
Checkout more Solutions here