Сложность: medium
Пиковым элементом называется элемент, который строго больше своих соседей.
Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков.
Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.
Необходимо написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
👨💻 Алгоритм:
1️⃣Начальная проверка:
Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.
2️⃣Определение направления поиска:
Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.
Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.
3️⃣Завершение поиска:
Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности.
😎 Решение:
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return self.search(nums, 0, len(nums) - 1)
def search(self, nums: List[int], l: int, r: int) -> int:
if l == r:
return l
mid = (l + r) // 2
if nums[mid] > nums[mid + 1]:
return self.search(nums, l, mid)
return self.search(nums, mid + 1, r)
Ставь 👍 и забирай 📚 Базу знаний