Find Peak Element

Средняя№162в гору

Дан массив, где соседние числа не равны. Пик — число больше своих соседей; за обоими краями −∞. Нужно вернуть индекс любого пика за O(log n). Наш пример: [2, 5, 9, 4, 3, 6, 8, 1] — пики 9 на индексе 2 и 8 на индексе 6; прогон возвращает 2.

162 Find Peak ElementРазбор · 1×

Пример: [2, 5, 9, 4, 3, 6, 8, 1] в виде столбиков. Стрелка — сравнение mid с соседом справа.

2051924334658617lo
ещё в диапазонесередина, проверяемотброшенопик

lo — первый индекс, 0

01/16
сначала · назад · пуск · шаг
Скорость
1function findPeakElement(nums):
2 lo = 0
3 hi = len(nums) - 1
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < nums[mid + 1]: // uphill
7 lo = mid + 1
8 else: // downhill: a peak at mid or before
9 hi = mid
10 return lo
состояние
lo
0
hi
–
mid
–
историянажмите шаг, чтобы вернуться

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

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

  1. За краями −∞, поэтому, идя в гору, всегда упрёшься в пик: склон не может расти бесконечно и обязан повернуть вниз, самое позднее за концом.
  2. Если nums[mid] < nums[mid + 1], справа подъём, и пик правее mid. Если нет, справа спуск: либо mid — пик, либо влево от него подъём, так что пик на mid или левее.
  3. Годится любой пик, поэтому можно отбросить половину, где тоже есть пик. Здесь первый шаг отбрасывает половину с 8 и поднимается к 9.

Сложность

Время O(log n): каждый шаг делит диапазон пополам. Память O(1): три индекса.

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

Решить на LeetCode ↗

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