Алгоритм чередования максимумов и минимумов в массиве: нестандартный подход

Вы когда-нибудь решали задачу на LeetCode, где нужно переставить отсортированный массив так, чтобы элементы чередовались: сначала максимум, потом минимум, затем второй максимум, второй минимум и так далее? Например, из [1, 2, 3, 4, 5] должно получиться [5, 1, 4, 2, 3]. Стандартное решение использует математический трюк с модулем, но есть более интуитивный способ — последовательное обращение суффиксов. Разберём этот алгоритм чередования максимумов и минимумов в массиве на Python.

Почему стандартное решение не всегда оптимально?

Обычно предлагают два подхода: временный массив (O(N) по времени и памяти) или трюк с модулем (O(N) по времени и O(1) по памяти). Модульный метод выглядит как математический трюк, а не как работа с массивом. Поэтому я нашёл альтернативу — последовательное обращение суффиксов. Этот метод использует только перестановки элементов, без кодирования значений.

Как работает последовательное обращение суффиксов

Идея проста: на каждом шаге мы переворачиваем суффикс массива, начиная с текущего индекса. После N таких операций массив сам выстраивается в нужном порядке. Разберём на примере [1, 2, 3, 4, 5]:

Шаг 1 (i=0): Переворачиваем весь массив: [5, 4, 3, 2, 1] — максимум на месте.
Шаг 2 (i=1): Переворачиваем суффикс с индекса 1: [5, 1, 2, 3, 4] — минимум на месте.
Шаг 3 (i=2): Переворачиваем суффикс с индекса 2: [5, 1, 4, 3, 2] — второй максимум на месте.
Шаг 4 (i=3): Переворачиваем суффикс с индекса 3: [5, 1, 4, 2, 3] — второй минимум на месте.

На последнем шаге (i=4) переворачивание одного элемента ничего не меняет. Итог: [5, 1, 4, 2, 3].

Реализация на Python с O(1) по памяти

Чтобы не использовать срезы (они создают копии), пишем ручной обмен через два указателя:

class Solution:
    def rearrange(self, arr):
        n = len(arr)
        for i in range(n):
            # Переворачиваем суффикс arr[i:]
            l = i
            r = n - 1
            while l < r:
                arr[l], arr[r] = arr[r], arr[l]
                l += 1
                r -= 1
        return arr

Здесь мы каждый раз переворачиваем суффикс, начиная с индекса i. Внешний цикл проходит по всем индексам, внутренний — меняет местами пары с двух концов.

Упрощённый вариант со срезами

Если не критично по памяти, можно использовать срезы и функцию reversed:

class Solution:
    def rearrange(self, arr):
        n = len(arr)
        for i in range(n):
            arr[i:] = reversed(arr[i:])
        return arr

Этот код короче, но создаёт временные списки при срезах.

Оценка сложности алгоритма

Время: O(N²) — мы делаем N переворотов, каждый в худшем случае занимает O(N). Для больших массивов это может быть медленно.

Память: O(1) для версии с указателями — мы не создаём дополнительных структур, только меняем элементы местами.

Когда применять этот метод?

На соревнованиях по программированию O(N²) часто не проходит по времени, поэтому для автоматических проверок лучше использовать модульный трюк. Однако этот метод полезен для понимания манипуляций с массивами и в задачах, где важна экономия памяти. Он также может быть хорошим упражнением для интервью: показывает, как можно решить задачу нестандартно.

Практический вывод: попробуйте прямо сейчас

Откройте редактор и реализуйте этот алгоритм на Python. Сначала напишите версию с указателями, затем упрощённую со срезами. Протестируйте на разных массивах, включая чётную и нечётную длину. Подумайте, как изменить алгоритм для несортированных массивов. Это поможет закрепить понимание работы с суффиксами и указателями.

Алгоритм чередования максимумов и минимумов в массиве