155 min stack
155. Min Stack
题目: https://leetcode.com/problems/min-stack/
难度:
Easy
思路一：
懒，直接用系统的数据结构 用lst和系统的heapq，提升一下，用deque和heapq,这样也没太大提升
from heapq import *
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.lst = []
self.h = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.lst.append(x)
heappush(self.h,x)
def pop(self):
"""
:rtype: void
"""
val = self.lst.pop()
self.h.remove(val)
heapify(self.h)
def top(self):
"""
:rtype: int
"""
return self.lst[-1]
def getMin(self):
"""
:rtype: int
"""
return self.h[0]
思路二：
参考http://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/
用两个stack，其中一个始终来记录到当前位置的最小值
When we insert 18, both stacks change to following.
Actual Stack
18 <--- top
Auxiliary Stack
18 <---- top
When 19 is inserted, both stacks change to following.
Actual Stack
19 <--- top
18
Auxiliary Stack
18 <---- top
18
When 29 is inserted, both stacks change to following.
Actual Stack
29 <--- top
19
18
Auxiliary Stack
18 <---- top
18
18
When 15 is inserted, both stacks change to following.
Actual Stack
15 <--- top
29
19
18
Auxiliary Stack
15 <---- top
18
18
18
When 16 is inserted, both stacks change to following.
Actual Stack
16 <--- top
15
29
19
18
Auxiliary Stack
15 <---- top
15
18
18
18
这样无论是用deque还是本身的lst都有一些提升
from collections import deque
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.lst = deque()
self.aux = deque()
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.lst.append(x)
if not self.aux or self.aux[-1] > x:
self.aux.append(x)
else:
self.aux.append(self.aux[-1])
def pop(self):
"""
:rtype: void
"""
self.lst.pop()
self.aux.pop()
def top(self):
"""
:rtype: int
"""
return self.lst[-1]
def getMin(self):
"""
:rtype: int
"""
return self.aux[-1]
