Premium

Массивы

Заменить элементы наибольшим справа

Заменить каждый элемент в массиве наибольшим элементом справа

Легкий

Постановка задачи

Описание (LeetCode)

Дан целочисленный массив arr, замените каждый элемент в этом массиве наибольшим среди элементов справа от него, последний элемент замените на -1. После выполнения замены верните этот массив.

Пример 1:

arr = [17, 18, 5, 4, 6, 1]

Результат:

[18, 6, 6, 6, 1, -1]

Пояснение:

  • индекс 0 --> наибольший элемент справа от индекса 0 имеет индекс 1 (18)
  • индекс 1 --> наибольший элемент справа от индекса 1 имеет индекс 4 (6)
  • индекс 2 --> наибольший элемент справа от индекса 2 имеет индекс 4 (6)
  • индекс 3 --> наибольший элемент справа от индекса 3 имеет индекс 4 (6)
  • индекс 4 --> наибольший элемент справа от индекса 4 имеет индекс 5 (1)
  • индекс 5 --> справа от индекса 5 нет элементов, поэтому используем -1

Пример 2:

arr = [400]

Результат:

[-1]

Пояснение:

Справа от индекса 0 нет элементов.

Ограничения:

  • 1 <= arr.length <= 10⁴
  • 1 <= arr[i] <= 10⁵

Решение

Это легкая задача на понимание прохода с конца - приема, который часто спасает, если нужно модифицировать массив "на месте" (in-place).

Наивное решение - это дополнительный поиск наибольшего элемента справа (вложенный цикл) от текущего элемента для каждого элемента массива (внешний цикл).

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

В таком решении "в лоб" (brute force, полный перебор) мы получим сложность O(n²), что неэффективно для больших массивов. На интервью вы можете предложить такое решение, но только как стартовую версию, которую сразу нужно будет улучшить.

Решение задачи "в лоб" может быть полезно, и не стоит сразу от него отмахиваться. Хотя такие решения почти всегда проигрывают по производительности, на практике их используют в нескольких сценариях: в тестировании, когда малы объемы данных, а также как базу для понимания задачи и улучшения алгоритма решения.

Давайте попытаемся найти более оптимальный подход.

Когда мы идем слева направо, для элемента i мы сканируем все элементы от i + 1 до конца и находим наибольший элемент, но при переходе к элементу i + 1 мы опять же сканируем все те же элементы от i + 2 до конца массива. Мы постоянно пересчитываем наибольший элемент на пересекающихся отрезках.

Давайте представим себе, что мы уже нашли наибольший элемент справа для i+1-го элемента в подмассиве arr[i+1 ... n-1]. Каким будет наибольший элемент справа для i-го элемента? Ясно, что это либо тот же самый наибольший элемент из arr[i+1 ... n-1], либо i+1-й элемент.

Переход от i+1 элемента к i-ому

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

В задачах на массивы, где результат элемента зависит от его правых соседей, всегда стоит задать себе вопрос: "А что, если пойти с конца?"

Если мы стоим в конце, мы уже "знаем" все о правой части, потому что мы ее только что прошли. Двигаясь справа налево "будущее" (то, что справа) становится для нас "прошлым" (тем, что мы уже видели).

Таким образом алгоритм заключается в том, чтобы двигаться справа налево, сохраняя значение самого большого встреченного элемента.

Основные шаги:

  1. Инициализируем переменную currentMax значением -1 (для последнего элемента правого соседа нет).
  2. Идем циклом с последнего индекса массива к нулевому:
    • Сохраняем текущее значение элемента во временную переменную.
    • Заменяем текущий элемент массива на currentMax.
    • Обновляем currentMax, выбирая максимум между старым значением и сохраненным элементом.
  3. Возвращаем измененный массив.

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

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

Временная сложность

Мы проходим по массиву ровно один раз с конца до начала с помощью одного цикла. Каждая итерация цикла выполняет операции с константным временем.

Таким образом, это линейная сложность: O(n).

Пространственная сложность

Мы используем фиксированное количество дополнительной памяти - это константная сложность: O(1).

Такое решение является оптимальным.

Код решения

Теперь можем написать код решения.

func replaceElements(arr []int) []int {
    currentMax := -1
    for i := len(arr) - 1; i >= 0; i-- {
        temp := arr[i]
        arr[i] = currentMax
        currentMax = max(currentMax, temp)
    }
    return arr
}

Итоги

В ходе разбора задачи мы перешли от интуитивного, но медленного подхода к оптимальному алгоритму. Вот главные выводы:

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

  2. Экономия ресурсов: благодаря модификации исходного массива "на месте" (in-place) и использованию всего одной вспомогательной переменной currentMax, мы добились константного O(1) потребления памяти.

  3. Универсальный паттерн: данная задача - это классический пример использования суффиксного максимума. Этот прием полезен в любых сценариях, где текущее решение зависит от состояния "будущих" элементов массива.

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

Войдите чтобы отмечать прогресс