Next Greater Element II

Средняя№503

Массив замкнут в круг: после последнего числа снова идёт первое. Для каждого числа найдите первое большее, если идти вперёд по кругу; если такого нет, ответ -1. Наш пример: [6, 2, 5, 1, 3] даёт [-1, 5, 6, 3, 6].

503 Next Greater Element IIРазбор · 1×

Пример: [6, 2, 5, 1, 3] по кругу. i проходит массив дважды, а j = i mod n — настоящий индекс; под числами ответы, в стеке индексы, которые ещё ждут.

0612253143numsanswerstack—
ещё не дошлиnums[j], текущее числождёт в стекепроверяемый верхследующее большее найдено

n = 5

01/57
сначала · назад · пуск · шаг
Скорость
1function nextGreaterElements(nums):
2 n = len(nums)
3 answer = list of n times -1
4 stack = empty stack // indices still waiting
5 for i from 0 to 2 * n - 1:
6 j = i mod n
7 while stack not empty and nums[j] > nums[top]:
8 answer[pop from stack] = nums[j]
9 if i < n:
10 push j onto stack
11 return answer
состояние
n
5
answer
–
stack
–
i
–
j
–
историянажмите шаг, чтобы вернуться

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

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

  1. Если идти по кругу от любого индекса, следующее большее не дальше n − 1 шагов. Два круга покрывают это для каждого индекса, включая последние.
  2. Первый круг кладёт каждый индекс один раз. Второй только отвечает тем, кто ещё ждёт: он ничего не кладёт, поэтому никто не получает ответ дважды и никто не ждёт сам себя.
  3. Что осталось в стеке после двух кругов — это самое большое число, возможно повторённое: во всём круге его никто не побил, поэтому -1 верно.

Сложность

Время O(n): 2n шагов цикла, и каждый индекс кладётся один раз и снимается не больше одного раза. Память O(n) на стек и ответ.

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

Решить на LeetCode ↗

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