Сложность: medium
Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.
Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].
Пример:
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
👨💻 Алгоритм:
1⃣Инициализация переменных:
Завести переменную count для подсчета числа изменений.
Проверить последовательность чисел в массиве nums.
2⃣Проверка условий:
Если nums[i] > nums[i + 1], то увеличиваем count.
Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.
Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.
3⃣Возврат результата:
Если количество изменений не превышает 1, вернуть true.
😎 Решение:
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
count = 0
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
if count > 0:
return False
count += 1
if i == 1 or nums[i] >= nums[i - 2]:
nums[i - 1] = nums[i]
else:
nums[i] = nums[i - 1]
return True
Ставь 👍 и забирай 📚 Базу знаний