Min Stack

Q: Как получить минимальное значение стека за время O(1)?

Записывайте минимум в момент добавления элемента. Стек изменяется только на вершине, поэтому минимум значений ниже любой высоты не может измениться, пока эта высота заполнена. Храните второй стек с минимумом на каждой высоте или только каждый новый минимум, и getMin станет чтением его вершины.

Q: Зачем добавлять значение в стек минимума, если оно равно текущему минимуму?

Потому что минимальное значение может находиться в стеке несколько раз. Если записывать только строго меньшие значения, две копии -2 будут использовать одну запись в mins . Первое извлечение -2 удалит эту запись, и тогда getMin сообщит о прежнем минимуме, хотя в стеке всё ещё останется вторая -2. Если записывать равные значения, у каждой копии будет своя запись.

Q: Можно ли реализовать стек с минимумом, используя O(1) дополнительной памяти?

Да, с помощью одного стека и одной переменной min . Когда вы помещаете x ниже текущего минимума, вместо него сохраните 2x - min и задайте min = x ; сохранённое число тогда меньше min , что служит меткой. Когда помеченное число извлекается, предыдущий минимум равен 2 * min - stored . При значениях, близких к пределам, арифметика выходит за пределы 32-битных целых чисел, поэтому нужны 64-битные значения, а логика знаков подвержена ошибкам; большинство интервьюеров вполне устраивает вариант с двумя стеками.

Q: Каковы временная и пространственная сложности стека с минимумом?

Каждая операция выполняется за O(1): push, pop, top и getMin считывают или изменяют только вершину одного или двух стеков. Для n сохранённых значений требуется O(n) памяти. Хранение минимума рядом с каждым значением всегда занимает 2n ячеек; хранение только новых минимумов занимает от n + 1 до 2n ячеек.

СреднеСтек

+10

Разработайте стек, который, помимо обычных операций push, pop и top, может сообщать наименьшее хранящееся в нём значение с помощью getMin. Каждая из четырёх операций должна выполняться за время O(1).

Вам заданы операции в порядке выполнения в ops, где args[i] содержит значение для операции push, а для любой другой операции — 0. Выполните их на одном стеке, изначально пустом, и верните по одной строке для каждой операции: "null" для push и pop, а для top и getMin — число в виде текста.

Функция

minStackOps(ops: string-array, args: integer-array) → string-array

opsstring-array: операции в порядке их выполнения
argsinteger-array: значение для каждой операции push, 0 для всех остальных операций
Возвращаетstring-array: один ответ для каждой операции в виде текста

Ограничения

1 ≤ ops.length ≤ 3000
args.length == ops.length
Каждое значение ops[i] — это push, pop, top или getMin.
-2³¹+1 ≤ args[i] ≤ 2³¹-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, добавляется в стек дважды. Первый вызов pop удаляет одну копию, а другая остаётся, поэтому getMin по-прежнему возвращает -2. Минимум возвращается к 3 только после второго вызова pop.

+16 скрытых тестов при отправке

Дополнительный вопрос

Можешь ли ты создать очередь, работающую по принципу «первым пришёл — первым вышел», которая также сообщает своё минимальное значение за амортизированное время O(1)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Обычный стек уже выполняет push, pop и top за O(1); сложность заключается в том, чтобы минимум сохранялся после извлечений. Ключевой факт: стек изменяется только на вершине. Пока значение находится на определённом уровне, ниже него ничего не меняется, поэтому минимум всех элементов до этого уровня фиксирован. Записывай этот минимум при добавлении элемента, и извлечение бесплатно восстановит предыдущий. Подходы различаются тем, что именно они записывают.

Просматривайте стек при каждом вызове getMin

Идея

Используй обычный стек для push, pop и top, а на запрос getMin отвечай, проверяя каждое хранящееся в нём значение и выбирая наименьшее. Это всегда правильно, потому что при вызове проверяется фактическое содержимое стека.

Это нарушает требование O(1). Вызов getMin для стека из n значений считывает все n значений. Скрытый тест, который добавляет в стек 1 500 значений и вызывает getMin после каждого добавления, считывает примерно 1 500 × 1 500 / 2 — больше миллиона значений, тогда как другие подходы считывают по одному значению за вызов. Система, выполняющая 10^5 таких операций, считала бы миллиарды значений.

Хранение одного минимального значения в кэше проблему не решает. Переменная с наименьшим значением подходит для добавления элементов, но после извлечения этого значения узнать следующее наименьшее без повторного просмотра всех значений невозможно.

Алгоритм

Сохрани значения в списке, используемом как стек.
Для 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

Храните минимальное значение рядом с каждым значением

Идея

Пока значение находится на высоте i в стеке, значения ниже него не могут измениться, поэтому наименьшее из нижних i значений остаётся неизменным, пока это значение там находится. Храни это число рядом с каждым значением: во втором стеке mins, где mins[i] — наименьшее из значений values[0..i].

При добавлении в стек новая запись в mins — это меньшее из x и записи под ней. При извлечении удали верхние элементы обоих стеков; вершина mins снова будет минимумом оставшихся значений. getMin считывает вершину mins.

В первом примере при добавлении в стек значений 4, 1 и 7 в стеке сохраняются минимумы 4, 1 и 1. Извлечение 7 оставляет 1 на вершине mins, а извлечение 1 оставляет 4. Каждая операция затрагивает только вершины двух стеков, поэтому выполняется за O(1). Цена — дополнительное число для каждого значения.

Алгоритм

Поддерживай два стека одинаковой высоты: values и mins.
Для push x добавь x в values, а в mins добавь меньшее из x и верхнего элемента mins (сам x, если mins пуст).
Для 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, и в mins будут храниться 1, 1, 1, 1. Повторяющаяся запись не сообщает ничего нового. Поэтому записывайте значение в mins только тогда, когда оно становится минимальным, и удаляйте его, когда это же значение покидает values.

При добавлении помещайте x в mins, если mins пуст или x меньше либо равен его верхнему элементу. При извлечении, если значение, покидающее values, равно верхнему элементу mins, извлеките элемент и из mins. Верхний элемент mins всегда является текущим минимумом: каждое значение, добавленное после него, либо больше, либо было меньше либо равно ему, тоже было записано и с тех пор извлечено.

Сравнение должно быть <=, а не <. Во втором примере -2 добавляется дважды. При < записывается только первая копия, первое извлечение удаляет её из mins, и getMin возвращает 3, хотя -2 всё ещё находится в стеке. При <= для каждой копии создаётся отдельная запись.

Все четыре операции по-прежнему выполняются за 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

Ловушки и крайние случаи

Эти ошибки связаны с копиями минимального значения и с тем, что удаляет операция pop.

Запись нового минимального значения только тогда, когда x строго меньше. Тогда в mins не хватает второй копии минимального значения, и удаление первой копии приводит к потере минимального значения, хотя вторая всё ещё находится в стеке. Это выявляет второй пример.
Хранение минимального значения в одной переменной. Это работает при добавлении элементов, но после удаления минимального значения переменная содержит устаревшее значение, а для поиска следующего наименьшего значения нужно просканировать стек.
Сравнение упакованных целых чисел по ссылке. В Java выражение Integer == Integer проверяет, являются ли оба операнда одним и тем же объектом. Для значений от -128 до 127 это случайно выполняется, поскольку Java кэширует их, а для большинства больших значений — нет, поэтому проверка при удалении элемента ломается только на больших значениях. Сначала преобразуйте их в int, как это сделано в коде на Java.
Удаление элемента из mins при каждом удалении элемента в третьем подходе. Размер этого стека уменьшается только тогда, когда удаляемое значение находится на его вершине; во втором подходе оба стека всегда изменяются синхронно.
Возврат числа для pop. В этом формате pop возвращает "null", как и push.

Частые вопросы4

Как получить минимальное значение стека за время O(1)?

Записывайте минимум в момент добавления элемента. Стек изменяется только на вершине, поэтому минимум значений ниже любой высоты не может измениться, пока эта высота заполнена. Храните второй стек с минимумом на каждой высоте или только каждый новый минимум, и getMin станет чтением его вершины.

Зачем добавлять значение в стек минимума, если оно равно текущему минимуму?

Потому что минимальное значение может находиться в стеке несколько раз. Если записывать только строго меньшие значения, две копии -2 будут использовать одну запись в mins. Первое извлечение -2 удалит эту запись, и тогда getMin сообщит о прежнем минимуме, хотя в стеке всё ещё останется вторая -2. Если записывать равные значения, у каждой копии будет своя запись.

Можно ли реализовать стек с минимумом, используя O(1) дополнительной памяти?

Да, с помощью одного стека и одной переменной min. Когда вы помещаете x ниже текущего минимума, вместо него сохраните 2x - min и задайте min = x; сохранённое число тогда меньше min, что служит меткой. Когда помеченное число извлекается, предыдущий минимум равен 2 * min - stored. При значениях, близких к пределам, арифметика выходит за пределы 32-битных целых чисел, поэтому нужны 64-битные значения, а логика знаков подвержена ошибкам; большинство интервьюеров вполне устраивает вариант с двумя стеками.

Каковы временная и пространственная сложности стека с минимумом?

Каждая операция выполняется за O(1): push, pop, top и getMin считывают или изменяют только вершину одного или двух стеков. Для n сохранённых значений требуется O(n) памяти. Хранение минимума рядом с каждым значением всегда занимает 2n ячеек; хранение только новых минимумов занимает от n + 1 до 2n ячеек.

Python

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"]

Min Stack

Функция

Ограничения

Примеры

Подсказки

Решение

Просматривайте стек при каждом вызове getMin

Храните минимальное значение рядом с каждым значением

Стек минимумов, который растёт только при появлении нового минимума

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи