Задача: 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 минут подряд.

😎 Решение:

public class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        int i;
        for (i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            return arr;
        }
        
        int j;
        for (j = n - 1; j > i; j--) {
            if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
                break;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        return arr;
    }
}

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