Извлечение минимального элемента в стеке в постоянное время

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

Всякий раз, когда вы push попадаете в стек, вы также проверяете, меньше ли этот элемент, чем предыдущий минимум, который сохраняется поверх minStack, а также подсчитывает, сколько этого элемента находится в стеке.

Если элемент меньше, то вы нажимаете на него (со счетом 1) на minStack. Если это то же самое, вы увеличиваете количество этого элемента на единицу.

Каждый раз, когда вы вытаскиваете предмет, если это самый маленький предмет в стеке (т.е. == minStack[-1][0]), вы уменьшаете количество самого маленького предмета. Если это количество становится равным нулю, вы вытаскиваете предмет из minStack. Теперь самый маленький предмет в стеке - это то, что было до того, как был добавлен первый предмет этого меньшего предмета. Это связано с тем, что для того, чтобы отбросить этот первый экземпляр самого маленького элемента, нам сначала нужно было выложить все на него сверху, по сути, свернув стек обратно к моменту времени, когда был добавлен самый маленький элемент.

PS: Когда вы пишете свои собственные реализации стека, знайте, что любой стек, который не возвращает элементы, которые он pop s, действует очень странно.