题目大意
#
要求:设计一个「栈」。实现 push
,pop
,top
,getMin
操作,其中 getMin
要求能在常数时间内实现。
解题思路
#
题目要求在常数时间内获取最小值,所以我们不能在 getMin
操作时,再去计算栈中的最小值。而是应该在 push
、pop
操作时就已经计算好了最小值。
我们有两种思路来解决这道题。
思路一:使用辅助栈保存当前栈中的最小值。在元素入栈出栈时,两个栈同步保持插入和删除。具体做法如下:
push
操作:当一个元素入栈时,取辅助栈的栈顶存储的最小值,与当前元素进行比较得出最小值,将最小值插入到辅助栈中;该元素也插入到正常栈中。
pop
操作:当一个元素要出栈时,将辅助栈的栈顶元素一起弹出。
top
操作:返回正常栈的栈顶元素值。
getMin
操作:返回辅助栈的栈顶元素值。
思路二:使用一个栈,保存元组:(当前元素值,当前栈内最小值)。具体操作如下:
push
操作:如果栈不为空,则判断当前元素值与栈顶元素所保存的最小值,并更新当前最小值,然后将新元素和当前最小值组成的元组保存到栈中。
pop
操作:正常出栈,即将栈顶元素弹出。
top
操作:返回栈顶元素保存的值。
getMin
操作:返回栈顶元素保存的最小值。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class MinStack:
def __init__(self):
self.stack = []
self.minstack = []
def push(self, val: int) -> None:
if not self.stack:
self.stack.append(val)
self.minstack.append(val)
else:
self.stack.append(val)
self.minstack.append(min(val, self.minstack[-1]))
def pop(self) -> None:
self.stack.pop()
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minstack[-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
class Node:
def __init__(self, x):
self.val = x
self.min = x
def push(self, val: int) -> None:
node = self.Node(val)
if len(self.stack) == 0:
self.stack.append(node)
else:
topNode = self.stack[-1]
if node.min > topNode.min:
node.min = topNode.min
self.stack.append(node)
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1].val
def getMin(self) -> int:
return self.stack[-1].min
|