Различные подходы к решению этой проблемы в JavaScript

Постановка проблемы:

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

Итак, как мы можем решить эту проблему?

Подход 1.Использование встроенных функций в JavaScript

  1. Инициализировать пустой массив result.
  2. Перебрать входной массив, кроме последнего элемента. Нам не нужно проверять последний элемент, так как он всегда будет заменен на -1.
  3. Для каждого индекса i цикла во входном массиве установите result[i] на следующий максимальный элемент справа.
  4. Следующий максимум находится с помощью Math.max(),.slice() и ... (spread operator).
// ES6 Arrow Function
const replaceMaxRight = arr => {
    const result = [];

    for(let i = 0; i < arr.length; i++) {
        result[i] = Math.max(...arr.slice(i+1));
    }

    result[result.length - 1] = -1;

    return result;
}

Временная сложность:O(N²)

Пространственная сложность:O(N)

Примечание. Хотя предыдущее решение работает, оно не самое эффективное, поскольку его временная сложность составляет O(N²). Однако мы можем улучшить временную сложность до O(N), перебирая массив справа налево. Давайте посмотрим на это в нашем втором подходе к решению этой проблемы.

Подход 2. Повторение входного массива справа налево.

  1. Инициализируйте переменную с именем max на -1. Эта переменная будет отслеживать максимальное количество найденных элементов.
  2. Повторите входной массив arr, начиная с самого правого элемента, потому что мы хотим отслеживать максимальное количество элементов, встречающихся до сих пор с правой стороны.
  3. Для каждой итерации инициализируйте переменную и сохраняйте значение элемента с текущим индексом arr[i] в эту переменную.
  4. Затем мы установим значение текущего индекса во входном массиве arr[i] на максимальное значение, которое мы видели до сих пор, которое хранится в переменной max .
  5. Наконец, мы обновим значение переменной max, сравнив текущее максимальное значение со значением, которое мы сохранили на шаге 3. Если сохраненное нами значение больше текущего максимального значения, мы соответствующим образом обновим переменную max.
// ES6 Arrow Functions
const replaceMaxRight = arr => {
    let max = -1;

    for(let i = arr.length - 1; i >= 0; i--) {
        let curr = arr[i];
        arr[i] = max;
        max = Math.max(max, curr);
    }

    return arr;
}

Временная сложность:O(N)

Пространственная сложность:O(1)

Примечание.Еще один способ кодирования проблемы, который немного отличается от второго подхода.

// ES6 Arrow Function
const replaceMaxRight = arr => {
    let max = arr[arr.length - 1];
    arr[arr.length - 1] = -1;

    for(let i = arr.length - 2; i >= 0; i--) {
        let curr = arr[i];
        arr[i] = max;
        if(curr > max) max = curr;
    }

    return arr;
}

Примечание.Время и Пространство сложности остаются такими же, как и в подходе 2.

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

Проблема - Leetcode 1299