心路历程：
这道题的难点在于加入最小值pop出去的话，怎么快速地找到下一个最小值。一个直观的想法是每次在push的时候都用链表把这些值给连上，按照从小到大的顺序。这样可以保证查找最小值的时间是常数，但是不能保证每次push和pop的时间复杂度。
用链表做了一下，主要是顺便复习了一下链表，这道题用链表的做法和LRU缓存那道题非常类似。
最好的做法是再构造一个最小辅助栈。这个栈的规则是：
入栈：辅助栈为空 或者 新加入的元素比辅助栈顶元素还小
出栈：数据栈出栈元素正好是辅助栈的栈顶元素
这样做的本质在于，我们不care ”后来的并且比前面来的值还大的元素“
注意的点：
1、链表的虚拟头结点对于链表的插入和删除操作是很有用的，核心概念就是while t.next: if … break else: t = t.next。需要每次访问t.next的元素，因此插入和删除都得依赖所寻求结点的前一个结点
2、链表的插入和删除都是三行：赋值temp + 重新赋值两个next （删除的话重新赋值一个None保证链表安全）
解法一：最小辅助栈
class MinStack(object):
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, x):
if not self.s2 or x <= self.getMin():
self.s2.append(x)
self.s1.append(x)
def pop(self):
if self.s1[-1] == self.getMin():
self.s2.pop()
self.s1.pop()
def top(self):
return self.s1[-1]
def getMin(self):
return self.s2[-1]
解法二：链表+栈
class MinStack:
def __init__(self):
from collections import deque
self.stack = deque([])
self.minlink = Node()
def push(self, val: int) -> None:
self.stack.append(val)
newnode = Node(val)
t = self.minlink
while t.next:
if t.next.val >= val:
break
t = t.next
# 此时插入到t后面的元素
temp = t.next
t.next = newnode
newnode.next = temp
def pop(self) -> None:
val = self.stack.pop()
# 删除链表中的元素val
t = self.minlink
while t.next:
if t.next.val == val:
break
t = t.next
assert t.next.val == val
temp = t.next.next
t.next.next = None
t.next = temp
return val
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minlink.next.val
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 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()
