Стек с поиском максимума / Habr

Несколько раз мне попадалась задача из разряда «собеседование в Google»:
нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция max(), возвращающая максимальный элемент за O(1) времени и с использованием O(1) дополнительной памяти (в сравнении со стеком без этой операции).

Предполагаю, что многие тоже о ней слышали, а может даже знакомы с каким-либо решением. Про решения я и предлагаю поговорить, там всё очень интересно.

Подробная формулировка

Чтобы точно не возникало вопросов, предлагаю сперва зафиксировать требуемые сигнатуры. Я буду использовать язык Java, но всё должно быть понятно даже если вы с ним не знакомы.

// Обычные методы стека.
void push(int value);
int pop();

// Дополнительный метод.
int max();

Решения с O(n)

Разберёмся с решениями задачи, которые используют ослабленные условия.

Если нам разрешено тратить O(n) времени, то поиск максимума можно реализовать банальным поиском в стеке. Скучно и неинтересно.
Если нам разрешено тратить O(n) памяти, но O(1) времени, то в качестве реализации можно использовать стек пар вида {value, max} — текущий элемент стека и текущий максимум стека. Или вообще сделать два стека, если совсем лень думать. Потребление памяти в таком подходе линейное. Тоже скучно и неинтересно.

Как решают задачу люди из интернета

Мне встречалось 2 решения. Они по своей сути эквивалентны, но на всякий случай приведу оба.

Решение 1

Воспользуемся тем фактом, что максимум всегда больше либо равен текущего элемента в стеке. То есть если отнять текущий элемент от текущего максимума, мы всегда получим число >= 0. Это даёт нам весь диапазон отрицательных чисел для кодирования чего-нибудь полезного, в случае если текущий элемент — максимальный. Например, мы можем закодировать предыдущий максимум.

Рассмотрим пример того, как в стек будут добавляться элементы:

stack := null

push 10:
  // На дне стека всегда 0.
  stack := {10 - 10 = 0} -> null
  max   := 10

push 7:
  // 7 меньше максимума, поэтому значение в стеке положительное.
  stack := {10 - 7 = 3} -> {10 - 10 = 0} -> null
  max   := 10

push 18:
  // 18 больше максимума, поэтому значение в стеке отрицательное.
  stack := {10 - 18 = -8} -> {10 - 7 = 3} -> {10 - 10 = 0} -> null
  max   := 18

Обратная операция удаления из стека осуществляется похожим образом:

stack = {10 - 18 = -8} -> {10 - 7 = 3} -> {10 - 10 = 0} -> null
max   = 18

pop, -8 < 0:
  result := max = 18
  max    := max + -8 = 10  // Вычислили предыдущий максимум.
  stack  := {10 - 7 = 3} -> {10 - 10 = 0} -> null

pop, 3 >= 0:
  result := max - 3 = 10 - 3 = 7
  max    := max = 10       // Не меняется.
  stack  := {10 - 10 = 0} -> null

pop, 0 >= 0:
  result := max - 0 = 10 - 0 = 10
  max    := max = 10       // Не меняется, но это не важно, стек пустой.
  stack  := null

Код решения 1:

Скрытый текст

public class MaxStack1 {
    static class Node {
        final int value;
        final Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node top;
    private int max;

    public void push(int value) {
        if (top == null) {
            top = new Node(0, null); // max - value == 0
            max = value;
        } else {
            top = new Node(max - value, top);
            max = Math.max(value, max);
        }
    }

    public int pop() {
        if (top == null) {
            throw new NoSuchElementException("Stack is empty");
        }

        Node oldTop = top;
        top = oldTop.next;

        if (oldTop.value >= 0) {
            return max - oldTop.value;
        } else {
            int res = max;
            max = max + oldTop.value;
            return res;
        }
    }

    public int max() {
        if (top == null) {
            throw new NoSuchElementException("Stack is empty");
        }

        return max;
    }
}

Решение 2

Оно уже более громоздкое, и построено на том же принципе — текущий элемент не может быть больше максимума. Но тут мы не будем вычислять разницу между value и max и сравнивать её с 0, мы сразу будем сравнивать value и max.

Если текущий элемент не максимальный, просто кладём его на вершину стека. Если же текущий элемент максимальный, то на вершину стека нужно положить какое-то значение, которое будет больше вставляемого value (которое станет новым max), по которому мы могли бы восстановить предыдущий максимум. Предлагается использовать следующую формулу:

value := 2 * value - max = value + (value - max)
max   := value

Здесь, конечно, делается небольшой финт ушами, который требует комментария:

Первое, что нужно заметить — это что value - max > 0. Помним, что value в этом контексте — это новый максимум.
Второе, что нужно заметить — это что value + (value - max) > value, то есть значение на вершине стека будет больше хранимого впоследствии значения max. Ровно то, чего хотели достичь.

Рассмотрим пример на тех же числах, что и раньше:

stack := null

push 10:
  // Тут нет предыдущего максимума, поэтому вставка
  // в пустой стек выглядит особым образом.
  stack := {10} -> null
  max   := 10

push 7:
  // 7 меньше максимума.
  stack := {7} -> {10} -> null
  max   := 10

push 18:
  // 18 больше максимума.
  stack := {2 * 18 - 10 = 26} -> {7} -> {10} -> null
  max   := 18

Доставать элементы будем так:

stack = {2 * 18 - 10 = 26} -> {7} -> {10} -> null
max   = 18

pop, 26 > 18:
  result := max = 18
  max    := 2 * max - 26 = 2 * 18 - 26 = 10 // Тут просто обратная формула.
  stack  := {7} -> {10} -> null

pop, 7 <= 10:
  result := 7
  max    := max = 10       // Не меняется.
  stack  := {10} -> null

pop, 10 <= 10:
  result := 10
  max    := max = 10       // Не меняется, но это не важно, стек пустой.
  stack  := null

Данный подход, если судить по примеру, проще первого, вот только формула может вызвать больше вопросов, поэтому я и описал его вторым. Код решения 2:

Скрытый текст

public class MaxStack2 {
    static class Node {
        final int value;
        final Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node top;
    private int max;

    public void push(int value) {
        if (top == null) {
            top = new Node(value, null);
            max = value;
        } else if (value <= max) {
            top = new Node(value, top);
        } else { // value > max
            top = new Node(2 * value - max, top);
            max = value;
        }
    }

    public int pop() {
        if (top == null) {
            throw new NoSuchElementException("Stack is empty");
        }

        Node oldTop = top;
        top = oldTop.next;

        if (oldTop.value <= max) {
            return oldTop.value;
        } else {
            int res = max;
            max = 2 * max - oldTop.value;
            return res;
        }
    }

    public int max() {
        if (top == null) {
            throw new NoSuchElementException("Stack is empty");
        }

        return max;
    }
}

Что не так с этими решениями?

Да вроде всё хорошо, если как на литкоде, брать -10⁷ <= x <= 10⁷. А если взять любой int, без читерских ограничений, которые обычно никем и не упоминаются?

Самое время рассказать, о чём эта статья на самом деле. Оба этих решения содержат очень похожие ошибки, которые я сейчас объясню.

Решение 1

Первое решение строилось на том свойстве, что если a >= b, то a - b >= 0. И наоборот, если a <= b, то a - b <= 0. А это, естественно, неправда!

Поскольку код я приводил на Java, мне проще считать, что все используемые числа — знаковые. С беззнаковыми типами нужно обращаться аккуратнее, но и на них можно было бы перенести все сделанные мною выводы.

Чтобы показать неверность указанного свойства, достаточно вспомнит�� про то, что числа "в компьютере" могут переполняться, и внезапно превращаться из положительных в отрицательные при, казалось бы, увеличении. Рассмотрим следующий пример:

a == Integer.MAX_VALUE, или же 2³¹-1
b == -1
a > b, очевидно
a - b == Integer.MAX_VALUE + 1 == Integer.MIN_VALUE < 0

Если взять числа, достаточно далеко расположенные друг от друга, то их разница может оказаться больше либо равной 2³¹ и переполнить целочисленный диапазон. А это сломает инварианты, необходимые для правильного восстановления значения в коде pop. При использовании -10⁷ <= x <= 10⁷ такого переполнения, конечно же, случиться не может.

В общем случае это решение — неверное.

Решение 2

Уже вооружившись нужным инструментом, показать ошибочность решения 2 будет ещё проще. В нём мы, помимо свойства из решения 1, полагались на то, что если b > 0,
то a + b > a. То есть совершили ту же самую ошибку дважды.

Контрпример будет почти идентичный:

a == Integer.MAX_VALUE
b == 1
b > 0, очевидно
a + b == Integer.MAX_VALUE + 1 == Integer.MIN_VALUE < a

Оно и понятно, всё же решения 1 и 2 мало отличаются что по подходу, что по требуемым предпосылкам. Итого оказывается, что нельзя просто так снять ограничения на входные данные и не упомянуть этого.

Почему?

Причина допущенной ошибки проста — авторы решений отождествляли свойства классической целочисленной арифметики и свойства 32-разрядной двоичной целочисленной арифметики. Делать этого ни в коем случае нельзя. Страшно даже представить, сколько из-за подобного мышления было совершено реальных ошибок в реальных проектах.

Казалось бы, в интернете кто-то не прав, и что с того? Если спросить меня об этом, то я скажу примерно следующее: одно дело, когда ты читаешь политические срачи в комментариях, и совершенно другое дело, когда ты читаешь образовательные материалы от людей, которые должны тебя чему-то учить. Авторы подобных образовательных материалов не выполнили свою работу должным образом и ввели читателей в заблуждение, это плохо.

Я спокойно могу себе представить собеседование в условный «Яндекс», на котором собеседующий мог бы дать эту конкретную задачу с неверными граничными условиями и буквально ожидать от собеседуемого неправильного решения. Ведь давайте будем честны — часто ли м�� настолько внимательно проверяем то, что прочитали в интернете, или скопировали из ответа на StackOverflow, к примеру? Нам тоже стоит помнить, что ответы в интернете пишут люди, которые могут ошибаться, даже если у ответа много плюсиков.

Но это я отвлёкся.

Как тогда выглядит правильное решение?

Вероятнее всего, никак. Мой тезис таков — при условиях O(1) времени и O(1) дополнительной памяти задача вообще не имеет решения.

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

Что общего между решениями 1 и 2, если посмотреть на них совсем абстрактно? То, что в дополнение к стеку с целыми числами они вводят ровно одну дополнительную целочисленную переменную. Я попробую обосновать, почему это — совершенно бесперспективный подход, для этого понадобится вспомнить немного информатики.

Чтобы было совсем наглядно, предлагаю работать не с 32-битными числами, а с 2-битными числами. Так же я буду их интерпретировать как беззнаковые числа, чтобы упросить понимание текста. Очевидно, что знаковость/беззнаковость интерпретации битов фундаментально ничего не меняет.

Если хранить максимум

Представим, что у нас есть 2-битное число на вершине стека (cur) и дополнительно хранимый 2-битный максимум (max). Хранение в дополнительной переменной какого-то значения, отличного от максимума, я прокомментирую позже. Суммарно это 4 бита информации.

Сколько информации нам нужно при выполнении операции pop? Рассмотрим все возможные варианты:

Максимум равен 0 (минимальное допустимое значение), текущее значение обязано тоже быть равным 0.
Максимум равен 1.
- Текущее значение может быть равно 0 или 1, предыдущий максимум всё ещё равен 1.
- Текущее значение равно 1 (текущий максимум), предыдущий максимум равен 0.
Максимум равен 2.
- Текущее значение может быть равно 0, 1 или 2, предыдущий максимум всё ещё равен 2.
- Текущее значение равно 2 (текущий максимум), предыдущий максимум равен 0 или 1.
Максимум равен 3.
- Текущее значение может быть равно 0, 1, 2 или 3, предыдущий максимум всё ещё равен 3.
- Текущее значение равно 3 (текущий максимум), предыдущий максимум равен 0, 1 или 2.

Итого, имеем (1) + (2 + 1) + (3 + 2) + (4 + 3) = 16 различных вариантов. Вплотную ровно для того, чтобы всё можно было уместить в 4 бита информации. Для больших разрядностей битов тоже будет хватать, причём также впритык.

Небольшая математическая выкладка для пояснения, приводится без доказательства:

$\sum_{k=1}^{n}{(2k-1)} = n^2$

В чём же проблема?

Проблема в том, как эта информация должна быть закодирована. Если переменная max хранит текущий максимальный элемент, то в случае, когда она равна 3 (максимальный из всех максимальных), мы оставшимися двумя битами должны покрыть 7 возможных исходов, а именно:

4 варианта текущего значения, если оно не максимально.
3 варианта значения предыдущего максимума.

Это просто невозможно сделать оставшимися двумя битами, и будет невозможно для всех разрядностей.

Что если кодировать данные иначе?

Представим, что у нас есть некое 2-битное значение на вершине стека (cur) и дополнительно хранимая 2-битная переменная (extra). Вместе они каким-либо способом образуют 4-х битное число, способное описать все требуемые нам 16 вариантов исхода. К примеру, мы просто пронумеровали все возможные исходы и поместили их в таблицу. Достаточно ли будет так поступить? Давайте думать.

Мы способны однозначно восстановить текущий элемент, текущий максимум и предыдущий максимум, используя данные нам 4 бита. Это уже хорошо. После того, как вершина стека будет удалена, нам требуется восстановить предыдущее состояние переменной extra, то есть какие-то 2 бита из выбранной нами нумерации.

Фактически, перед нами встала ровно та же проблема, что была при наличии переменной max вместо extra. Если выяснится то, что предыдущий максимум должен быть равен 3 (исходя из текущего состояния вершины стека), то после удаления текущей вершины стека у нас появится ровно 2 бита дополнительной информации (элемент в стеке), чтобы различить всё те же 7 вариантов, повторю их:

4 варианта текущего значения, если оно не максимально.
3 варианта значения предыдущего максимума.

Получается очень забавно. У нас достаточно бит информации, но в них тупо не хватает энтропии (так часто бывает в неверных решениях задач про рычажные весы и монетки). Судя по всему, иная кодировка данных не способна фундаментально ничего изменить. Без дополнительных бит в стеке у нас не хватает информации, а дополнительные биты — это уже O(n) дополнительной памяти.

Что если мы расширим количество бит в переменной extra? Лучше не станет. На вершине стека то всё ещё 2 бита, их не будет хватать.

Конечно, есть ненулевой шанс того, что и я всё напутал и пришёл к неверным выводам. Ошибаюсь, бывает. Но я правда не вижу здесь места для ошибки, так что всех несогласных приглашаю к диалогу в комментариях, вместе мы найдём истину.

Что в итоге

Если в задаче не задаются должным образом ограничения на входные значения, то это очень плохо, ведь буквально от этого зависит то, какие алгоритмы применимы для решения, а какие неприменимы. На том же литкоде ограничения пишут не просто так, и если ты видишь работу с массивами длиной в миллион, то скорее всего наивный алгоритм с O(n^2) не прокатит. Тут почти то же самое.

Люди в интернете, которые стараются вас чему-то научить, могут про такие ограничения забыть. Вряд-ли специально. Когда я впервые ознакомился с решением данной задачи про стек, оно как раз было преподнесено мне в виде «должно работать для всех значений int».

Так что будьте аккуратны с целыми числами и граничными условиями. Спасибо за внимание!