Сложность: medium
Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].
Пример:
Input: arr = [3,2,1]
Output: [3,1,2]
👨💻 Алгоритм:
1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.
2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.
3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.
😎 Решение:
def prevPermOpt1(arr):
n = len(arr)
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
break
else:
return arr
for j in range(n - 1, i, -1):
if arr[j] < arr[i] and (j == n - 1 or arr[j] != arr[j + 1]):
break
arr[i], arr[j] = arr[j], arr[i]
return arr
Ставь 👍 и забирай 📚 Базу знаний