Мы уже знаем стек как структуру «последним пришёл — первым ушёл». Оказывается, если поддерживать в стеке упорядоченность, он решает целый класс задач, которые иначе требуют вложенных циклов.

Речь о вопросах вида: «для каждого дня — через сколько дней впервые будет выручка больше?», «какой ближайший столбец слева выше этого?», «какой самый большой прямоугольник помещается под гистограммой?».

Проблема

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

for (int i = 0; i < revenue.length; i++) {
    for (int j = i + 1; j < revenue.length; j++) {
        if (revenue[j] > revenue[i]) { answer[i] = j - i; break; }
    }
}

Это O(N²). Причём работа делается многократно: если выручка долго падает, каждый день заново пробегает один и тот же хвост.

Идея: очередь ожидающих

Заметим: пока выручка падает, каждый новый день ничем не помогает предыдущим — он ведь меньше. Все они «ждут» дня, который окажется выше. А когда такой день наконец приходит, он закрывает сразу всех, кто ниже него.

Значит, нужно хранить дни, которые ещё ждут своего роста. И хранить их удобно стеком: последний пришедший — самый свежий и самый низкий, он же и закроется первым.

static int[] daysToGrow(int[] revenue) {
    int[] answer = new int[revenue.length];
    Deque<Integer> waiting = new ArrayDeque<>();
    for (int i = 0; i < revenue.length; i++) {
        while (!waiting.isEmpty() && revenue[i] > revenue[waiting.peek()]) {
            int day = waiting.pop();
            answer[day] = i - day;
        }
        waiting.push(i);
    }
    return answer;
}

В стеке лежат индексы, а не значения: индекс позволяет и достать выручку, и посчитать расстояние в днях. Дни, оставшиеся в стеке в конце, так и не дождались роста — у них в ответе ноль, и он уже там, потому что массив в Java заполнен нулями.

Стек здесь монотонный: сверху вниз выручка в нём возрастает. Каждый новый день перед добавлением «срезает» всё, что ниже его.

Почему это линейно, хотя внутри цикл

Смущает while внутри for — выглядит как O(N²). Но посчитаем не итерации, а операции со стеком: каждый день кладётся в стек ровно один раз и снимается не больше одного раза. Значит, суммарное число снятий по всему проходу не превышает N, сколько бы их ни случилось на отдельном шаге.

Такой способ считать называется амортизированной оценкой: отдельный шаг бывает дорогим, но общая работа ограничена. Итог — O(N) по времени и O(N) по памяти в худшем случае, когда данные монотонно убывают и никто не закрывается до самого конца.

Строгое или нестрогое сравнение

В коде стоит revenue[i] > revenue[waiting.peek()] — строго больше. Это не мелочь.

Если поставить >=, равные значения начнут закрывать друг друга, и на данных {5, 5, 5} первый день получит ответ «через один день», хотя роста не было — выручка осталась той же. Выбор между > и >= определяется формулировкой: «строго больше» или «не меньше». Это самое частое место ошибки в приёме, и проверять его надо на данных с повторами.

Направление тоже настраивается: чтобы искать ближайший больший слева, идут по массиву справа налево; чтобы искать меньший — переворачивают знак сравнения.

Монотонная очередь

Родственный приём — когда нужен максимум в скользящем окне. Стека уже мало: элементы уходят не только сверху (их вытеснил больший), но и снизу (они выпали из окна). Берут очередь с доступом с обоих концов — тот же ArrayDeque:

  • с хвоста убирают всех, кто меньше нового элемента (они больше никогда не станут максимумом);
  • с головы убирают тех, кто вышел за левый край окна;
  • максимум окна всегда лежит в голове.

Время тоже O(N) и по той же причине: каждый элемент входит и выходит по разу.

Как узнать приём в задаче

  • В условии есть слова «ближайший больший», «следующий меньший», «через сколько шагов впервые».
  • Наивное решение — вложенный цикл, который бежит вперёд или назад до первого подходящего.
  • Нужен максимум или минимум в скользящем окне — это монотонная очередь.
  • Задача про прямоугольники под гистограммой или про воду между столбиками — классические переодетые формы того же приёма.

Коротко

  • Монотонный стек хранит элементы, ещё ожидающие ответа, в упорядоченном виде; новый элемент закрывает сразу всех, кого превзошёл.
  • Хранят индексы, а не значения: по индексу доступны и значение, и расстояние.
  • Время O(N) несмотря на вложенный цикл: каждый элемент кладётся и снимается не более одного раза.
  • Строгое > или нестрогое >= выбирается по формулировке; на данных с повторами ошибка проявляется сразу.
  • Родственный приём — монотонная очередь для максимума в скользящем окне: убирает с хвоста меньших, с головы выпавших из окна.

Дальше — динамическое программирование: что делать, когда ответ складывается из ответов на меньшие версии той же задачи.