class MinStack:
# main idea: use two stacks to store 1:regular pushed elements 2: record min vals
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minStack = []
def push(self, x: int) -> None:
self.stack.append(x)
if self.minStack:
top = self.minStack[-1]
if x <= top:
self.minStack.append(x)
else:
self.minStack.append(x)
def pop(self) -> None:
pop = self.stack.pop()
top = self.minStack[-1]
if pop == top:
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
# 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()
solution2
class MinStack:
# main idea: use one stack, use one min varible to record min val; push min val intu stack before update new min_val
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = float('inf')
def push(self, x: int) -> None:
if x <= self.min:
self.stack.append(self.min)
self.min = x
self.stack.append(x)
def pop(self) -> None:
top = self.stack.pop()
if top == self.min:
self.min = self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min
solution 3
class Node:
def __init__(self,val,min):
self.val = val
self.min = min
self.next = None
class MinStack:
# main idea: use node to record min val at current moment
# step 1: initialze head
def __init__(self):
"""
initialize your data structure here.
"""
self.head = None
# step 2.1: check if head null, if not => compare with head.min, update min; step2 add new node to the head
def push(self, x: int) -> None:
if not self.head: # if stack is empty, min = x
self.head = Node(x,x)
else:
# optimize node = Node(x,min(self.head.min,x))
if self.head.min >= x: # if nex val is smaller or equal than min
node = Node(x,x)
else:
node = Node(x, self.head.min) # each node will record the min val at its point
node.next = self.head
self.head = node
def pop(self) -> None:
self.head = self.head.next
def top(self) -> int:
return self.head.val
def getMin(self) -> int:
return self.head.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()