Напишите функцию, которая проверяет, можно ли сделать массив целых чисел неубывающим, изменив не более одного элемента.
nums = [1, 2, 3] --> True (since already in non-decreasing order) nums = [3, 2, 1] --> False (since need to modify at least 2 elements) nums = [1, 2, 0] --> True (since can just modify last element) nums = [2, 3, 1, 2] --> False (since need to modify at least 2 elements)
Сможете ли вы сделать это за O(n) времени и O(1) пространства? Возьмите ручку и бумагу и попробуйте.
Рассуждение
Элемент a[i] проблематичен, когда он > a[i+1]. Это означает, что необходимо изменить либо a[i], либо a[i+1].
Через один проход, если мы находим более 1 проблемного элемента, это означает, что нам нужно изменить как минимум 2 элемента. Следовательно, мы можем безопасно вернуть false .
Если мы находим только один проблемный элемент, это не значит, что мы всегда можем сделать одно изменение в массиве, чтобы сделать его неубывающим.
nums = [2, 3, 1, 2] based on the a[i] > a[i+1] check, there is only one problematic element, which is 3, but we cannot simply modify one element in the array to make it non-decreasing
Итак, мы должны выяснить условия, которые позволяют только одну модификацию, если есть только один проблемный элемент.
В приведенных ниже примерах показаны различные условия. Ось Y представляет возрастающие числа, а ось X представляет индекс массива. a представляет массив.
a[i+1] — последний элемент. В этом случае мы можем просто изменить последний элемент на >= a[i].
a[i] — первый элемент. В этом случае мы можем просто изменить его на <= a[i+1] .
a[i-1] <= a[i+1] . В этом случае мы можем изменить a[i] так, чтобы он находился между его соседями.
a[i] <= a[i+2] . В этом случае мы можем изменить a[i+1] так, чтобы он находился между его соседями.
Решение в коде
Этот вопрос учит нас думать о различных перестановках массива и наблюдать за случаями, когда возможна одна модификация.
Существует ли лучшее решение? Озвучьте в комментариях ниже.
Надеюсь, вам понравилось.
Спасибо.
Вечнозеленое кодирование
