Диагностика задачи без названия паттерна

Выпускная практика начинается с паузы перед решением. Сначала прочитайте несколько условий, запишите свою гипотезу и только затем открывайте разбор. Здесь название приёма не является подсказкой: важнее увидеть, что повторяется в медленном решении и какую информацию действительно нужно хранить.

Три условия, которые пока нельзя называть паттерном

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

Карточка A

Дан массив дневных температур. Для каждого дня верните число дней до первого более тёплого дня справа; если такого дня нет, верните 0. Пример: для [73,74,75,71,69,72,76,73] ответ [1,1,4,2,1,1,0,0]. Размер массива может достигать 100000.

Карточка B

Дана строка из круглых скобок. Нужно найти длину самой длинной корректной непрерывной части. Пример: для “)()())” ответ 4. Нельзя менять порядок символов.

Карточка C

Для каждого здания дана высота. Нужно для каждого здания найти первое справа здание выше него; если такого нет, вернуть -1. Нужно вернуть индексы, а не сами высоты.

В своей записи отдельно предскажите: 1) что вы храните; 2) когда оно удаляется; 3) почему один индекс не обрабатывается бесконечно; 4) чем проверить гипотезу на равных значениях.

Раскрытие медленного ориентира

Раскрытие A — после собственной записи

Для каждого дня можно идти вправо, пока не встретится большая температура. Это верный эталон, но в убывающем массиве он делает почти n² / 2 сравнений.

Раскрытие B — после собственной записи

Можно перебрать все границы подстроки и проверять её баланс. Это медленно, но помогает заметить, что символы слева иногда ещё ждут подходящую пару справа.

Раскрытие C — после собственной записи

Для каждого здания прямой поиск первого более высокого справа также квадратичен. У A и C одна форма «первый будущий объект, который проходит порог», хотя предметные слова различаются.

Где повторный просмотр уже не даёт новой информации

В A день с температурой 73 будет снова проверяться многими будущими днями, хотя после первого дня теплее 73 его ответ окончательно известен. Нужен список индексов, ответы которых ещё не определены; он должен позволять быстро отвечать на вопрос: «кого текущая температура закрывает прямо сейчас?»

Раскрытие A: какие дни должны ждать справа

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

Это называется монотонным стеком индексов. Название полезно только после рассуждения: стек нужен потому, что закрываются именно самые недавние ещё не закрытые дни, а не произвольные.

Что всегда верно для ожидающих индексов

После обработки дня i стек содержит ровно те индексы j <= i, для которых более тёплого дня среди j+1..i ещё не было. Температуры на индексах стека идут невозрастающе. Поэтому, если вершина холоднее temperatures[i], её первый подходящий день — именно i: более ранние дни уже проверены, а между ней и i не осталось тёплого кандидата.

Каждый индекс кладётся один раз и снимается не более одного раза. Это одновременно доказательство корректности и ключ к линейной сложности.

Как получить ответы за один проход

1. Создайте массив ответов из нулей и пустой стек индексов без ответа.
2. Читайте дни слева направо.
3. Пока вершина стека холоднее текущего дня, снимайте её и записывайте разность индексов.
4. Положите индекс текущего дня в стек.
5. Индексы, оставшиеся в стеке в конце, уже имеют правильный ноль: более тёплого дня справа не существует.

Код после собственного объяснения

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

C++17

#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

vector<int> daysUntilWarmer(const vector<int>& temperatures) {
    vector<int> answer(temperatures.size(), 0);
    vector<int> waiting;

    for (int day = 0; day < static_cast<int>(temperatures.size()); ++day) {
        while (!waiting.empty() &&
               temperatures[waiting.back()] < temperatures[day]) {
            int previousDay = waiting.back();
            waiting.pop_back();
            answer[previousDay] = day - previousDay;
        }
        waiting.push_back(day);
    }
    return answer;
}

int main() {
    assert(daysUntilWarmer({73, 74, 75, 71, 69, 72, 76, 73}) ==
           vector<int>({1, 1, 4, 2, 1, 1, 0, 0}));
    assert(daysUntilWarmer({70, 70, 70}) == vector<int>({0, 0, 0}));
    assert(daysUntilWarmer({90, 80, 70}) == vector<int>({0, 0, 0}));
    cout << "ok\n";
}

Python 3

def days_until_warmer(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    waiting: list[int] = []

    for day, current in enumerate(temperatures):
        while waiting and temperatures[waiting[-1]] < current:
            previous_day = waiting.pop()
            answer[previous_day] = day - previous_day
        waiting.append(day)

    return answer


assert days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]) == [
    1, 1, 4, 2, 1, 1, 0, 0
]
assert days_until_warmer([70, 70, 70]) == [0, 0, 0]
assert days_until_warmer([90, 80, 70]) == [0, 0, 0]
print("ok")

Как честно оценить один проход

Хотя внутри цикла есть while, каждый индекс добавляется в стек один раз и снимается максимум один раз. Значит, всего операций со стеком O(n), время O(n), память O(n) в строго убывающем массиве. В отличие от него прямой перебор имеет O(n²) времени и O(1) дополнительной памяти.

Где ошибка в одном знаке меняет задачу

• Равные температуры не должны закрывать ответ: нужен строгий знак <, потому что требуется более тёплый день.
• Убывающий массив оставляет все ответы нулевыми.
• Пустой массив возвращает пустой массив.
• Если условие просит первое значение не ниже, знак меняется на <=, и это уже другая задача.

Четыре тренировки перед новым условием

Отладка

Замените в уме < на <= и прогоните [70,70]: ошибочный код вернёт [1,0] вместо [0,0]. Такой тест проверяет смысл неравенства, а не случайную арифметику.

Границы

Проверьте [], [42], строго убывающий и строго возрастающий массивы. У последнего ожидайте много снятий со стека за один день.

Сложность

Объясните, почему while не превращает алгоритм в O(n²): назовите, сколько раз может быть снят индекс 5.

Объяснение вслух

За 45 секунд скажите: «Стек содержит дни без найденного более тёплого дня; как только приходит температура выше вершины, она является первым подходящим днём для вершины». После этого добавьте, почему вершина, а не любой индекс.

Какие слова в условии должны насторожить

Ищите «первый справа/слева», «ближайший больше или меньше», «ждёт следующий объект, проходящий порог», а также большой n. Сначала проверьте, что кандидаты можно закрывать по мере чтения входа; затем сформулируйте порядок их ожидания.

Когда список ожидающих индексов не решает задачу

Он не подходит, если нужен максимум на произвольном отрезке, число всех пар или первый объект при нетранзитивном сравнении. Если будущий объект имеет стоимость, а не просто проходит порог, может понадобиться другая модель. Не выбирайте стек по слову «справа»: сначала убедитесь, что закрываемые кандидаты образуют упорядоченную границу.

Самопроверка: равные значения

Вопрос: почему индекс дня с 70 нельзя снять, когда приходит ещё один день с 70?
Ответ: новый день не более тёплый. Снятие означало бы, что ответ для первого дня уже найден, но его значение должно остаться 0 или дождаться температуры выше 70.

Самопроверка: альтернативный путь

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

Диагностируем три условия до названия техники

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

Самостоятельно выбираем паттерн для двух условий

Не используйте конспект, названия техник или подсказки. После решения запишите медленный эталон, состояние, инвариант, альтернативу и оценку.

Задача 1

Для каждого элемента массива найдите первый индекс справа с меньшим значением или -1. Ограничения: n <= 200000; значения могут повторяться и быть отрицательными.

Задача 2

Дана строка из скобок трёх типов. Верните индекс первого символа, после которого уже невозможно получить корректную последовательность, или -1, если такой позиции нет. Сформулируйте контракт для пустой строки.

Что переносить на новое условие

Не угадывайте ярлык. Спросите, какой медленный поиск повторяет сравнения, какие ответы ещё ждут будущего входа и что делает ответ окончательным. Если можете назвать это состояние, его инвариант и жизненный цикл, название структуры становится вторичным.