Сложность: medium
Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].
Пример:
Input: arr = [3,2,1]
Output: [3,1,2]
👨💻 Алгоритм:
1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.
2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.
3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.
😎 Решение:
fun prevPermOpt1(arr: IntArray): IntArray {
val n = arr.size
var i = n - 2
while (i >= 0 && arr[i] <= arr[i + 1]) {
i--
}
if (i == -1) return arr
var j = n - 1
while (arr[j] >= arr[i] || (j < n - 1 && arr[j] == arr[j + 1])) {
j--
}
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
return arr
}Ставь 👍 и забирай 📚 Базу знаний