Next Greater Element I

Лёгкая№496

Даны два массива из различных чисел, и каждое число из nums1 есть где-то в nums2. Для каждого числа из nums1 найдите его в nums2 и возьмите первое число правее, которое больше; если такого нет, ответ -1. Наш пример: nums1 = [4, 7, 2], nums2 = [4, 1, 3, 7, 2, 5] даёт [7, -1, 5].

496 Next Greater Element IРазбор · 1×

Пример: nums1 = [4, 7, 2], nums2 = [4, 1, 3, 7, 2, 5]. Один проход по nums2 заполняет greater — он нарисован под каждым числом; в стеке числа, которые ещё ждут. Потом каждое число из nums1 — один поиск в словаре.

041123374255nums2greaterstack—nums1472answer
ещё не дошлитекущее числождёт в стекепроверяемый верхследующее большее найдено

Пустой словарь: число → следующее большее за ним в nums2

01/36
сначала · назад · пуск · шаг
Скорость
1function nextGreaterElement(nums1, nums2):
2 greater = empty map // number → next greater
3 stack = empty stack
4 for x in nums2:
5 while stack not empty and x > top of stack:
6 greater[pop from stack] = x
7 push x onto stack
8 answer = empty list
9 for y in nums1:
10 if y in greater: append greater[y] to answer
11 else: append -1 to answer
12 return answer
состояние
greater
{}
stack
–
x
–
y
–
answer
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Число ждёт в стеке, пока не придёт первое число больше; оно его и снимает — это и есть следующее большее. В стеке числа к верху только убывают, поэтому большее снимает их сверху вниз, и цикл останавливается на первом, которое не меньше нового.
  2. Все числа различны, поэтому ключом словаря может быть само число, и в стеке можно держать числа, а не индексы.
  3. У числа, оставшегося в стеке в конце, дальше нет большего. В словарь оно не попадает, и поиск даёт -1.

Сложность

Время O(n + m), где n — длина nums2, m — длина nums1: каждое число из nums2 кладётся в стек один раз и снимается не больше одного раза, а поиск в словаре — O(1). Память O(n) на словарь и стек.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.