Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.pop() -- Removes the element on top of the stack.top() -- Get the top element.getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
Subscribe to see which companies asked this question
class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.stack = [] self.min_val = None self.min_idx = None def push(self, x): """ :type x: int :rtype: void """ if self.min_val is None: self.min_val = x self.min_idx = 0 # exclude repulicated values self.stack.append(x) elif x < self.min_val: self.min_val = x self.stack.append(x) self.min_idx = len(self.stack) - 1 else: self.stack.append(x) def pop(self): """ :rtype: void """ # is poped value is min_val if self.min_idx == len(self.stack) -1: # Probability is 1/n new_stack = self.stack[:-1] if new_stack: # O(n) some times self.min_val = min(new_stack) self.min_idx = new_stack.index(self.min_val) else: self.min_val = None self.min_idx = None self.stack.pop() if len(self.stack) == 0: self.min_val = None self.min_idx = None def top(self): """ :rtype: int """ return self.stack[-1] def getMin(self): """ :rtype: int """ return self.min_val # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()
