Поиск пиковых элементов

Решение: Поиск пиковых элементов

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

Определение пикового элемента

• Элемент в середине массива — пиков, если больше левого И правого соседей
• Первый элемент — пик, если больше второго (не учитываем несуществующего левого соседа)
• Последний элемент — пик, если больше предпоследнего (не учитываем несуществующего правого соседа)
• Массив из одного элемента — этот элемент всегда пик

Алгоритм решения (наивный)

1. Обработираем первый элемент: если он больше второго (или массив из одного элемента) — это пик
2. Проходим по средним элементам: проверяем каждый элемент с обоих сторон
3. Обрабатываем последний элемент: если он больше предпоследнего — это пик
4. Возвращаем все найденные пики

Реализация (простой подход)

def findPeakElements(nums: list) -> list:
    """
    Находит все пиковые элементы в массиве.
    
    Args:
        nums: Входной массив целых чисел
    
    Returns:
        Список пиковых элементов
    """
    if not nums:
        return []
    
    peaks = []
    n = len(nums)
    
    # Случай: один элемент
    if n == 1:
        return nums
    
    # Проверяем первый элемент
    if nums[0] > nums[1]:
        peaks.append(nums[0])
    
    # Проверяем средние элементы
    for i in range(1, n - 1):
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            peaks.append(nums[i])
    
    # Проверяем последний элемент
    if nums[n - 1] > nums[n - 2]:
        peaks.append(nums[n - 1])
    
    return peaks

Пошаговый разбор примера

Вход: [1, 3, 2, 4, 1, 5, 2]

Индекс 0 (элемент 1):

• 1 > 3? Нет → не пик

Индекс 1 (элемент 3):

• 3 > 1 И 3 > 2? Да → пик ✓

Индекс 2 (элемент 2):

• 2 > 3 И 2 > 4? Нет → не пик

Индекс 3 (элемент 4):

• 4 > 2 И 4 > 1? Да → пик ✓

Индекс 4 (элемент 1):

• 1 > 4 И 1 > 5? Нет → не пик

Индекс 5 (элемент 5):

• 5 > 1 И 5 > 2? Да → пик ✓

Индекс 6 (элемент 2):

• 2 > 5? Нет → не пик

Выход: [3, 4, 5] ✓

Оптимизированная версия с индексами

def findPeakIndices(nums: list) -> list:
    """
    Возвращает индексы пиковых элементов вместо самих элементов
    """
    if not nums:
        return []
    
    peaks = []
    n = len(nums)
    
    if n == 1:
        return [0]
    
    # Первый элемент
    if nums[0] > nums[1]:
        peaks.append(0)
    
    # Средние элементы
    for i in range(1, n - 1):
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            peaks.append(i)
    
    # Последний элемент
    if nums[n - 1] > nums[n - 2]:
        peaks.append(n - 1)
    
    return peaks

Версия с использованием вспомогательной функции

def findPeakElements_helper(nums: list) -> list:
    """
    Версия с вспомогательной функцией для проверки пика
    """
    def is_peak(index):
        n = len(nums)
        
        # Проверяем левого соседа
        if index > 0 and nums[index] <= nums[index - 1]:
            return False
        
        # Проверяем правого соседа
        if index < n - 1 and nums[index] <= nums[index + 1]:
            return False
        
        return True
    
    peaks = []
    for i in range(len(nums)):
        if is_peak(i):
            peaks.append(nums[i])
    
    return peaks

Тестовые случаи

# Основной пример
print(findPeakElements([1, 3, 2, 4, 1, 5, 2]))  # [3, 4, 5]

# Граничные случаи
print(findPeakElements([]))              # []
print(findPeakElements([1]))             # [1]
print(findPeakElements([1, 2]))          # [2]
print(findPeakElements([2, 1]))          # [2]
print(findPeakElements([1, 2, 1]))       # [2]

# Все элементы возрастают
print(findPeakElements([1, 2, 3, 4, 5]))  # [5]

# Все элементы убывают
print(findPeakElements([5, 4, 3, 2, 1]))  # [5]

# Несколько пиков подряд (хотя технически невозможно)
print(findPeakElements([1, 3, 3, 2, 1]))  # []

# Чередующийся паттерн
print(findPeakElements([1, 3, 1, 3, 1]))  # [3, 3]

# Все одинаковые элементы
print(findPeakElements([2, 2, 2, 2]))    # []

Сложность

• Временная сложность: O(n), один проход по массиву
• Пространственная сложность: O(k), где k — количество пиков (не считаем выходной массив)

Важные детали

• Граничные элементы обрабатываются отдельно
• Соседство имеет значение — элемент должен быть больше ВСЕ соседей
• Равные элементы не образуют пик (требуется строгое неравенство >)
• Пустой массив возвращает пустой список
• Массив из одного элемента всегда содержит пик

Решение оптимально по времени и подходит для production-кода. На практике используются более сложные подходы с бинарным поиском O(log n) только для поиска одного пика, но для поиска всех пиков требуется O(n).