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 elementvalonto 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,topandgetMinoperations will always be called on non-empty stacks. - At most
3 * 104calls will be made topush,pop,top, andgetMin.
SOLUTION:
import heapq
# class MinStack:
# def __init__(self):
# self.stack = []
# self.heap = []
# self.deleted = {}
# def push(self, val: int) -> None:
# heapq.heappush(self.heap, val)
# self.stack.append(val)
# def pop(self) -> None:
# popped = self.stack.pop()
# self.deleted[popped] = self.deleted.get(popped, 0) + 1
# def top(self) -> int:
# return self.stack[-1]
# def getMin(self) -> int:
# curr = self.heap[0]
# while curr in self.deleted:
# heapq.heappop(self.heap)
# self.deleted[curr] -= 1
# if self.deleted[curr] == 0:
# del self.deleted[curr]
# curr = self.heap[0]
# return curr
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
self.stack.append((val, min(self.stack[-1][1], val) if len(self.stack) > 0 else val))
def pop(self) -> None:
return self.stack.pop()[0]
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
Top comments (0)