Min Stack
设计一个栈，除了常见的 push、pop 和 top，还可以通过 getMin 报告栈中最小的值。四种操作都必须在 O(1) 时间内完成。
你会按顺序获得操作列表 ops，其中 args[i] 在执行入栈操作时保存对应的值，在执行其他操作时均为 0。在一个初始为空的栈上依次执行这些操作，并为每个操作返回一个字符串："null" 表示 push 和 pop，top 和 getMin 则返回文本形式的数字。
函数
- opsstring-array
- 按运行顺序排列的操作
- argsinteger-array
- 每次入栈对应的值，其他所有操作都为 0
- 返回值string-array
- 每次操作对应一个答案，以文本形式
约束条件
1 ≤ ops.length ≤ 3000args.length == ops.length- 每个
ops[i]都是push、pop、top或getMin。 -231+1 ≤ args[i] ≤ 231-1（入栈时），其他任何操作时args[i] == 0。pop、top和getMin只会在栈中至少有一个值时调用。
示例
- 输入
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- 输出
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- 解释
- 从底部向上，栈中依次是 4、1 和 7，所以最小值是 1。弹出 7 后，1 就到了栈顶。再弹出 1 后，栈中只剩下 4，所以最小值又变回 4。
- 输入
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- 输出
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- 解释
- 最小值 -2 被压入了两次。第一次弹出会移除一个副本，另一个仍然存在，所以
getMin仍为 -2。只有第二次弹出后，最小值才会恢复为 3。
- 输入
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- 输出
- ["null", "null", "null", "null", "2", "8"]
- 解释
- 0 被压入栈中后又被弹出，因此它不再计入。此时栈中有 2 和 8：栈顶是 8，最小值是 2。
进阶
你能构建一个先进先出队列，并让它在摊还 O(1) 时间内报告最小值吗？
提示
逐个打开提示，每个都会多透露一点。
一个变量存储最小值，这种方法在你弹出这个最小值之前都有效。弹出时，你需要知道什么？你可以在什么时候把它记下来？
栈只会在栈顶发生变化，因此只要某一高度仍有元素，该高度以下的值中的最小值就会保持不变。入栈时记录最小值。
在这些值旁边再维护一个栈。当新值小于或等于它的栈顶时，将新值压入这个栈；当离开主栈的值等于它的栈顶时，将它弹出。这样，它的栈顶始终就是
getMin的答案。
题解
普通栈已经可以在 O(1) 时间内执行 push、pop 和 top。栈只会在顶部发生变化，所以当一个值位于某个高度时，从栈底到该高度的所有值中的最小值是固定的。在入栈时记录这个最小值，出栈时就能免费恢复之前的最小值。
每次调用 getMin 时都扫描栈
思路
通过扫描每个已存储的值来实现 getMin。这种方法始终正确，因为它读取的是实际内容，但对 n 个值调用一次 getMin，就要读取全部 n 个值。执行 1,500 次 push 操作，每次之后都调用一次 getMin，读取次数就会超过一百万次，而其他方法每次调用只读取一个值。
只缓存一个最小值并不能解决问题。弹出这个值后，你需要扫描才能找到下一个最小值。
算法
- 将这些值存储在用作栈的列表中。
- 对于
push x，追加x；对于pop，移除最后一个值；对于top，读取它。 - 对于
getMin，遍历存储的每个值，并返回最小值。 - 将每个答案记录为文本，并返回列表。
class MinStack:
def __init__(self):
self.values = []
def push(self, x):
self.values.append(x)
def pop(self):
self.values.pop()
def top(self):
return self.values[-1]
def getMin(self):
# Look at every stored value: O(n).
smallest = self.values[0]
for v in self.values:
if v < smallest:
smallest = v
return smallest
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result将最小值存储在每个值旁边
思路
再维护一个栈 mins，其中 mins[i] 是 values[0..i] 中的最小值。压入时，存储 x 和它下面那一项中较小的值。弹出时，同时移除两个栈的栈顶，此时 mins 的栈顶又是剩余元素中的最小值。在第一个示例中，压入 4、1 和 7 时，存储的最小值依次为 4、1 和 1；弹出 7，再弹出 1 后，剩下 4。
每个操作只会访问两个栈的栈顶，因此每个操作的时间复杂度都是 O(1)。代价是每个值都要多存储一个数字。
算法
- 维护两个高度相同的栈：
values和mins。 - 对于
push x，将x压入values，然后将x和mins栈顶中较小的值压入mins（如果mins为空，则压入x）。 - 对于
pop，将两个栈都弹出一个元素。 - 对于
top，读取values的栈顶；对于getMin，读取mins的栈顶。 - 将每个答案记录为文本，并返回列表。
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # mins[i] is the smallest of values[0..i]
def push(self, x):
self.values.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.values.pop()
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result仅在出现新的最小值时才增长的最小值栈
思路
在第二种方法中，mins 经常会重复记录：依次压入 1、7、8 和 9，它就会存储 1、1、1、1。因此，只有当一个值成为最小值时，才将它记录到 mins 中，也就是 mins 为空或 x 小于等于它的栈顶时；当同一个值从 values 中移出时，也从 mins 中弹出它。
mins 的栈顶始终是最小值：之后压入的任何值，要么比它大，要么小于等于它并被记录在 mins 中，这种情况下该值之后已经被弹出。使用 <=，这样最小值的每个副本都会有自己的条目。所有四种操作的时间复杂度仍为 O(1)，只有当值按从大到小的顺序到来时，mins 才会和 values 一样高。
算法
- 维护一个
values栈和一个mins栈。 - 对于
push x，将x压入values。如果mins为空，或者x小于或等于栈顶元素，也将x压入mins。 - 对于
pop，弹出values的栈顶元素。如果弹出的值等于mins的栈顶元素，也弹出mins的栈顶元素。 - 对于
top，读取values的栈顶元素；对于getMin，读取mins的栈顶元素。 - 将每个答案记录为文本，并返回列表。
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # each value that was a minimum when pushed; the top is the current minimum
def push(self, x):
self.values.append(x)
# <= keeps one copy per equal minimum, so popping one leaves the others.
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.values.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result
易错点和边界情况
- 只有当
x严格更小时，才记录新的最小值。在第二个示例中，两个 -2 副本共用mins中的一项，第一次弹出会将其移除；此时栈中仍有一个 -2，但getMin返回 3。 - 在第三种方法中，每次弹出时都弹出
mins中的值。只有当被移除的值等于它的栈顶值时，mins才会缩小。 - 在 Java 中使用
Integer == Integer比较装箱后的整数。它检查对象是否为同一对象，这对 -128 到 127 之间的缓存值成立，但对大多数更大的值不成立。请先拆箱为int。 - 让
pop返回一个数字。在这种格式中，pop和push一样，返回"null"。
常见问题3
如何在 O(1) 时间内获取栈中的最小值？
在存储值的栈旁边再维护一个栈，用来记录每个高度对应的最小值，或者只记录每个新出现的最小值。这样，getMin 就可以读取这个栈的栈顶，而每次入栈和出栈都会以 O(1) 的时间复杂度更新两个栈。
Min Stack 能用 O(1) 的额外空间实现吗？
可以，只用一个栈和一个变量 min。要把 x 压入 min 之下，就存储 2x - min，它小于 x，并且会标记该条目，然后设置 min = x。弹出标记条目 s 时，可以恢复旧的最小值，即 2 * min - s。接近 32 位范围的边界时，需要使用 64 位值。
Min Stack 的时间复杂度和空间复杂度是多少？
每种操作的时间复杂度都是 O(1)：push、pop、top 和 getMin 每次只读取或更改一个或两个栈的顶部。对于存储 n 个值的情况，空间复杂度为 O(n)。在每个值旁边都存储最小值始终会使用 2n 个位置；只存储新的最小值则会使用 n + 1 到 2n 个位置。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def minStackOps(ops, args):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
预期输出
["null", "null", "null", "1", "null", "1", "null", "4"]