Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

Input: arr = [3,2,1]
Output: [3,1,2]

👨‍💻 Алгоритм:

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.

3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.

😎 Решение:

function prevPermOpt1(arr) {
    const n = arr.length;
    let i;
    for (i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            break;
        }
    }
    if (i === -1) {
        return arr;
    }
    
    let j;
    for (j = n - 1; j > i; j--) {
        if (arr[j] < arr[i] && (j === n - 1 || arr[j] !== arr[j + 1])) {
            break;
        }
    }
    
    [arr[i], arr[j]] = [arr[j], arr[i]];
    
    return arr;
}

Ставь 👍 и забирай 📚 Базу знаний