Сложность: medium
Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].
Пример:
Input: arr = [3,2,1]
Output: [3,1,2]
👨💻 Алгоритм:
1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.
2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.
3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.
😎 Решение:
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& arr) {
int n = arr.size();
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;
}
}
swap(arr[i], arr[j]);
return arr;
}
};Ставь 👍 и забирай 📚 Базу знаний