python - 在恒定时间内检索堆栈中的最小元素

Question

你能帮我理解这行代码发生了什么吗？

def push(self, x):
    self.stack.append(x)
    if len(self.minStack):
        if x < self.minStack[-1][0]:
            self.minStack.append([x, 1])
        elif x == self.minStack[-1][0]:
            self.minStack[-1][1] += 1
    else:
        self.minStack.append([x, 1])

取自此代码行:

class MinStack2:
    def __init__(self):
        self.stack, self.minStack = [], []

    # @param x, an integer
    # @return an integer

    def push(self, x):
        self.stack.append(x)
        if len(self.minStack):
            if x < self.minStack[-1][0]:
                self.minStack.append([x, 1])
            elif x == self.minStack[-1][0]:
                self.minStack[-1][1] += 1
        else:
            self.minStack.append([x, 1])

您还可以在这个 GitHub 帐户中找到它:https://github.com/kamyu104/LeetCode/blob/master/Python/min-stack.py

提前谢谢

如果对您有任何误解，请不要随意标记。而是留下反馈。这是一个学习平台，我觉得在没有解释的情况下标记帖子是非常没有受过教育的

Answer 1

每当您插入到堆栈上时，您还会检查该项目是否小于之前的最小值(该最小值保存在minStack的顶部)以及堆栈中有多少该项目。

如果该项目较小，则将其(计数为 1)推送到 minStack 上。如果相同，则将该项目的计数加一。

每次弹出一个项目时，如果它是堆栈中最小的项目(即 == minStack[-1][0])，则会减少最小项目的计数。如果该计数变为零，则将该项从 minStack 中弹出。现在，堆栈中最小的项目就是添加第一个较小项目之前的内容。这是因为为了丢弃最小项目的第一个实例，我们必须首先弹出它上面的所有内容，本质上是将堆栈回滚到添加最小元素的时间点。

PS:当您发现自己编写自己的堆栈实现时，请知道任何不返回其 pop 的项的堆栈都会表现得非常奇怪。