题目大意
#
要求：设计一个「栈」。实现 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
|