665. 非递减数列
题目描述
输入一个长度为 n 的整数数组 nums。
若对所有 0 <= i <= n - 2 都有 nums[i] <= nums[i + 1]，就称数组是非递减的。
你最多可以修改一个元素的值（也可以不改）。判断能否借此使数组变为非递减，能则返回 true，否则返回 false。
示例 1
输入：nums = [4,2,3] 输出：true
解释：把开头的 4 改成 1 即可。
示例 2
输入：nums = [4,2,1] 输出：false
解释：无论改哪一个元素，都无法让它变为非递减。
数据范围
n == nums.length1 <= n <= 10^4-10^5 <= nums[i] <= 10^5
解题思路
从左到右找“下降点” nums[i] < nums[i-1]。出现第二个下降点就一定做不到。对第一个下降点，要么把 nums[i-1] 降下来，要么把 nums[i] 升上去。优先降 nums[i-1]（改成 nums[i]），这样右边的数最小、对后面最友好；但如果 nums[i] 比 nums[i-2] 还小，降 nums[i-1] 会在 i-2 处产生新的下降，只能把 nums[i] 升到 nums[i-1]。
为什么正确
处理完下标 i 后，经过至多 cnt 次修改的 nums[0..i] 是非递减的，且 nums[i] 是所有可行修改方式中最小的末尾值。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
只数下降点个数不够：[3,4,2,3] 只有一个“相邻下降”却做不到；必须真的修改数组，并根据 nums[i-2] 选择修改哪一边。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
cnt = 0
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
cnt += 1
if cnt > 1:
return False
if i >= 2 and nums[i] < nums[i - 2]:
nums[i] = nums[i - 1]
else:
nums[i - 1] = nums[i]
return Trueclass Solution {
public boolean checkPossibility(int[] nums) {
int cnt = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
cnt++;
if (cnt > 1) {
return false;
}
if (i >= 2 && nums[i] < nums[i - 2]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
}
return true;
}
}class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int cnt = 0;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] < nums[i - 1]) {
cnt++;
if (cnt > 1) {
return false;
}
if (i >= 2 && nums[i] < nums[i - 2]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
}
return true;
}
};func checkPossibility(nums []int) bool {
cnt := 0
for i := 1; i < len(nums); i++ {
if nums[i] < nums[i-1] {
cnt++
if cnt > 1 {
return false
}
if i >= 2 && nums[i] < nums[i-2] {
nums[i] = nums[i-1]
} else {
nums[i-1] = nums[i]
}
}
}
return true
}var checkPossibility = function(nums) {
let cnt = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
cnt++;
if (cnt > 1) {
return false;
}
if (i >= 2 && nums[i] < nums[i - 2]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
}
return true;
};function checkPossibility(nums: number[]): boolean {
let cnt = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
cnt++;
if (cnt > 1) {
return false;
}
if (i >= 2 && nums[i] < nums[i - 2]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
}
return true;
}