Find Peak Element

Q: Какова временная сложность Find Peak Element?

Бинарный поиск выполняется за время O(log n) и использует O(1) памяти; для 5000 значений требуется не более 13 шагов. Проход слева направо имеет сложность O(n) , поскольку он может прочитать каждую пару, прежде чем обнаружит убывание.

Q: Продолжает ли бинарный поиск работать, когда пиков несколько?

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

Q: Пик всегда является наибольшим значением?

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

СреднеБинарный поиск

+10

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

Верни индекс пика за время O(log n).

Функция

findPeakElement(nums: integer-array) → integer

numsinteger-array: значения, повышающиеся до одного пика, а затем снижающиеся
Возвращаетinteger: индекс пика

Ограничения

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] для каждого допустимого i.
nums строго возрастает до одного индекса и строго убывает после него, поэтому существует ровно один пик.

Примеры

Ввод: nums = [2, 5, 9, 4, 1]
Вывод: 2
Пояснение: Значения поднимаются через 2, 5 и 9, затем опускаются через 4 и 1. Поворотная точка — 9, индекс 2.

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

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

Подсказки

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

Открыто 0 из 3

Решение

При наличии единственного пика он является наибольшим значением, поэтому за один проход его можно найти за O(n). Чтобы получить O(log n), сравнивайте nums[mid] с nums[mid+1]: наклон в точке mid показывает, по какую сторону от пика она находится, поэтому на каждом шаге можно отбросить половину диапазона.

Идите, пока значения не начнут снижаться

Идея

До пика каждое значение меньше следующего, а после пика каждое значение больше. Поэтому пик — это первый индекс i, для которого nums[i] > nums[i+1], или последний индекс, если массив только возрастает.

Когда пик находится в конце массива из 5000 значений, при последовательном проходе выполняется 4999 сравнений, тогда как бинарному поиску требуется 13.

Алгоритм

Для i от 0 до n-2 сравните nums[i] с nums[i+1].
При первом i, для которого nums[i] больше, верните i.
Если цикл завершился без убывания, верните n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Бинарный поиск по наклону

Идея

Сравните одну пару: nums[mid] и nums[mid+1]. Подъём означает, что массив продолжает расти, а в этом массиве это происходит только до пика: пик находится в позиции mid+1 или правее. Спуск означает, что вы находитесь на пике или за ним: пик находится в позиции mid или левее.

Поддерживайте диапазон [lo, hi], в котором всегда находится пик. При подъёме передвигайте lo в позицию mid+1. При спуске передвигайте hi в позицию mid, оставляя mid, поскольку это может быть пик. Когда lo совпадёт с hi, оставшийся индекс и будет пиком. Округление mid вниз оставляет его меньше hi, поэтому mid+1 всегда существует.

В первом примере при mid = 2 получаем 9 > 4, поэтому hi = 2; затем при mid = 1 получаем 5 < 9, поэтому lo = 2 — это и есть пик. Для 5000 значений потребуется не более 13 шагов.

Алгоритм

Установи lo = 0 и hi = n-1.
Пока lo < hi, вычисли mid = lo + (hi - lo) / 2, округлив вниз.
Если nums[mid] < nums[mid+1], установи lo = mid + 1.
Иначе установи hi = mid.
Верни lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

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

Установка hi = mid - 1 при движении вниз. В [2, 5, 9, 4, 1] первое значение mid — это сама вершина, а hi = 1 отбрасывает её; поиск возвращает 1.
Сравнение с nums[mid-1] при округлении mid вниз. Значение mid может быть равно 0, и тогда левого соседа нет.
Использование полуоткрытого диапазона с hi = n. Тогда mid может быть равен n-1, и nums[mid+1] обращается за пределы массива — это происходит сразу, если в нём всего одно значение.
Забыть о сдвиге в Lua и R. Ответ всё ещё является индексом с отсчётом от 0, поэтому позиция i возвращается как i-1.

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

Какова временная сложность Find Peak Element?

Бинарный поиск выполняется за время O(log n) и использует O(1) памяти; для 5000 значений требуется не более 13 шагов. Проход слева направо имеет сложность O(n), поскольку он может прочитать каждую пару, прежде чем обнаружит убывание.

Продолжает ли бинарный поиск работать, когда пиков несколько?

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

Пик всегда является наибольшим значением?

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

def findPeakElement(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [2, 5, 9, 4, 1]

Ожидаемый вывод