Next Greater Element I

Q: Какова временная сложность задачи Next Greater Element I?

Решение с монотонным стеком работает за время O(n + m) , где n — длина nums2 , а m — длина nums1 . Каждое значение nums2 помещается в стек и извлекается из него не более одного раза, а для каждого значения nums1 выполняется один поиск в отображении. Для отображения и стека требуется O(n) памяти. Поиск справа от каждого значения занимает O(n·m) времени.

ЛегкоМонотонный стек Хеширование

+10

Даны два массива различных целых чисел, nums1 и nums2, причём каждое значение из nums1 также встречается в nums2. Следующий больший элемент значения x — это первое расположенное справа от x в nums2 значение, которое больше x, или -1, если такого значения нет.

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

Функция

nextGreaterElement(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: значения, которые нужно указать в ответе, все они найдены в nums2
nums2integer-array: массив, в котором вы ищете справа от каждого значения
Возвращаетinteger-array: следующий больший элемент для каждого значения из nums1 или -1, в порядке следования nums1

Ограничения

1 ≤ nums1.length ≤ nums2.length ≤ 10⁴
0 ≤ nums1[i], nums2[i] ≤ 10⁴
Все значения в nums1 различны, и все значения в nums2 различны.
Каждое значение из nums1 встречается в nums2.

Примеры

Ввод: nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
Вывод: [8, -1, 6]
Пояснение: После 3 в nums2 идут 8 и 2, и 8 — первое число, которое больше 3. После 8 следует только 2, поэтому для 8 получается -1. Значение сразу после 1 — 6, оно уже больше.

Ввод: nums1 = [5, 2]nums2 = [2, 9, 5, 4]
Вывод: [-1, 9]
Пояснение: Только 4 следует за 5, и 4 меньше, поэтому 5 получает -1. Значение сразу после 2 — 9. Ответы следуют в порядке nums1, а не в порядке nums2.

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

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

Для каждой позиции в nums2 можешь вернуть, сколько шагов вправо находится её следующий больший элемент, за тот же единственный проход?

Подсказки

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

Открыто 0 из 3

Решение

Для одного значения ответ можно найти, просканировав элементы справа от него, но поиск для каждого значения из nums1 требует до nums1.length × nums2.length шагов. Ответы зависят только от nums2, поэтому можно сразу найти следующий больший элемент для каждого значения из nums2 с помощью монотонного стека, сохранить их в хеш-таблице и найти ответы для nums1 по ключу.

Найдите каждое значение и просматривайте вправо

Верно, но не успевает на самых больших тестах

Идея

Следуй определению. Для значения x из nums1 проходи по nums2, пока не дойдёшь до x. Затем продолжай идти и остановись на первом значении, которое больше x. Если дойдёшь до конца и не найдёшь такого значения, ответ — -1.

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

Этот способ работает медленно, если ответы находятся далеко или отсутствуют. Если значения в nums2 убывают, ни один проход не найдёт большего значения, и для каждого значения из nums1 придётся идти до конца. При m значениях в nums1 и n в nums2 это до m × n шагов: 10^8, если оба массива содержат по 10^4 значений. Кроме того, каждый проход повторно просматривает участки, по которым уже прошли предыдущие проходы.

Алгоритм

Переберите каждое значение x из nums1.
Найдите индекс j, где nums2[j] равно x.
Просматривайте nums2 начиная с j+1 и остановитесь на первом значении, большем x.
Добавьте это значение или -1, если просмотр дошёл до конца.
Верните собранные ответы.

def nextGreaterElement(nums1, nums2):
    result = []
    for x in nums1:
        j = 0
        while nums2[j] != x:
            j += 1
        answer = -1
        for k in range(j + 1, len(nums2)):
            if nums2[k] > x:
                answer = nums2[k]
                break
        result.append(answer)
    return result

Монотонный стек и хеш-таблица

Идея

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

Проследим за nums2 = [1, 6, 3, 8, 2]. Добавьте 1 в стек. Затем приходит 6 и превосходит 1, поэтому для 1 ответом будет 6; добавьте 6 в стек. Затем приходит 3, не превосходит 6 и добавляется сверху: стек — [6, 3]. Затем 8 извлекает 3 и 6, поэтому для обоих ответом будет 8; добавьте 8 в стек. Затем добавляется 2. В конце в стеке [8, 2], и для этих двух значений ответа нет. Для nums1 = [3, 8, 1] отображение даёт [8, -1, 6].

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

Каждое значение nums2 добавляется в стек один раз и извлекается не более одного раза, поэтому за весь проход внутренний цикл выполняет не более n извлечений. С учётом m поисков временная сложность составляет O(n + m). Связь между двумя массивами обеспечивает отображение: значения уникальны, поэтому значение можно безопасно использовать в качестве ключа, даже если в nums1 и nums2 оно находится на разных позициях. В решениях на C и R для отображения используется массив из 10^4+1 ячеек, индексируемых по значению; это работает, потому что ни одно значение не превышает 10^4.

Алгоритм

Создай пустую карту и пустой стек.
Для каждого значения nums2 снимай с вершины стека все меньшие значения и сопоставляй их с текущим значением.
Помести текущее значение в стек.
Для каждого значения nums1 верни соответствующий ему ответ или -1, если его нет.

def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []  # values still waiting for a greater one, decreasing from bottom to top
    for value in nums2:
        # value is the first greater value to the right of every smaller value on the stack.
        while stack and stack[-1] < value:
            next_greater[stack.pop()] = value
        stack.append(value)
    # Whatever is still on the stack has no greater value to its right.
    return [next_greater.get(x, -1) for x in nums1]

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

Сам стек — это короткий код; ошибки связаны с тем, что и где вы записываете.

Запись наибольшего значения справа вместо первого большего. В nums2 = [3, 5, 1, 2, 4, 9, 0] ответ для 1 — 2, а не 9.
Возврат ответов в порядке nums2 или для каждого значения nums2. Результат содержит по одной записи на каждое значение nums1, в его порядке.
Возврат индекса вместо значения. Задача просит вернуть само большее значение.
Чтение nums2 по индексу, который значение имеет в nums1. Одно и то же значение находится на разных позициях в двух массивах; найдите его по значению — для этого и нужна карта.
Забыть о значениях, оставшихся в стеке в конце. Они так и не встретили большее значение, поэтому ответ для них — -1; поиск в карте без значения по умолчанию завершится ошибкой или ничего не вернёт.
Поиск влево или переход к началу nums2. Учитываются только значения справа, и массив не зацикливается.

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

Какова временная сложность задачи Next Greater Element I?

Решение с монотонным стеком работает за время O(n + m), где n — длина nums2, а m — длина nums1. Каждое значение nums2 помещается в стек и извлекается из него не более одного раза, а для каждого значения nums1 выполняется один поиск в отображении. Для отображения и стека требуется O(n) памяти. Поиск справа от каждого значения занимает O(n·m) времени.

Что такое монотонный стек?

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

Почему для задачи Next Greater Element I нужна хеш-таблица?

Обход стека выдаёт ответы в порядке извлечения значений из стека, используя значения nums2 в качестве ключей. Результат должен следовать порядку nums1, где те же значения находятся на других позициях. Поскольку все значения различны, отображение значений в ответы связывает два массива, обеспечивая поиск каждого значения за постоянное время.

Что изменится, если nums2 циклический?

Затем поиск большего значения может продолжиться с начала массива. Выполни тот же обход массива с помощью стека дважды, используя индекс i % n для i от 0 до 2n-1, и добавляй значения в стек только во время первого прохода. Значения, которые остаются в стеке после обоих проходов, не имеют большего значения нигде, поэтому ответ для них — -1.

Python

def nextGreaterElement(nums1, nums2):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums1 = [3, 8, 1]
nums2 = [1, 6, 3, 8, 2]

Ожидается

[8, -1, 6]