155. Min Stack
- Total Accepted: 96784
- Total Submissions: 383098
- Difficulty: Easy
- Contributors: Admin
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.
Code
import sys
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.min = sys.maxint
self.stk = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
if x <= self.min:
self.stk.append(self.min)
self.min = x
self.stk.append(x)
def pop(self):
"""
:rtype: void
"""
if self.stk:
if self.stk[-1] == self.min:
self.min = self.stk[-2]
self.stk.pop()
self.stk.pop()
def top(self):
"""
:rtype: int
"""
if self.stk:
return self.stk[-1]
def getMin(self):
"""
:rtype: int
"""
if self.stk:
return self.min
# 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()
Idea
Whenever self.min changes, push the old self.min into stack. When popping an element equal to self.min, then the previous element in the stack is self.min before the element was added.
You can also add self.min along with the new element every time you execute push: https://discuss.leetcode.com/topic/11985/my-python-solution