665.非递减数列.md

665. 非递减数列

url

题目

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

输入：nums = [1,2,2,4]
输出：[2,3]
输入：nums = [1,1]
输出：[1,2]

方法

思路如下：

• 如果出现 a[i] > a[i+1] 改变一个数 就面临两种选择
  • 1. 把a[i]变大
  • 1. 把a[i+1] 变小
• 这两种选择其实是有依据的 需要比较a[i-1] 与 a[i+1]的值 eg. ... 1 4 3 ... 只能选择把4变小 ... 3 4 1 ... 只能选择把1变大
• 改变完之后，记录改变次数，再检测是否升序
• 如果次数大于1，至少改了两次 返回false
• 先让前两个有序
• 因为没有左边没有数 所以对于前两个数来说，最佳选择就是吧 a[0] 变小

code

js

let checkPossibility = nums => {
    let cnt = 0;
    for (let i = 1; i < nums.length && cnt < 2; i++) {
        if (nums[i] >= nums[i - 1])
            continue;
        cnt++;
        // 关键在这里
        if (i - 2 >= 0 && nums[i - 2] > nums[i])
            nums[i] = nums[i - 1];
        else
            nums[i - 1] = nums[i];
    }
    return cnt <= 1;
};
console.log(checkPossibility([4 ,2 ,3]));
console.log(checkPossibility([4 ,2, 1]));

go

func checkPossibility(nums []int) bool {
	cnt := 0
	for i := 1; i < len(nums) && cnt < 2; i++ {
		if nums[i] >= nums[i-1] {
			continue
		}
		cnt++
		if i-2 >= 0 && nums[i-2] > nums[i] {
			nums[i] = nums[i - 1]
		} else {
			nums[i - 1] = nums[i]
		}
	}
	return cnt <= 1
}

java

class Solution {
    public boolean checkPossibility(int[] nums) {
        int cnt = 0;
        for (int i = 1; i < nums.length && cnt < 2; i++) {
            if (nums[i] >= nums[i-1]) continue;
            cnt++;
            // 关键在这里呀
            if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
                nums[i] = nums[i - 1];
            } else {
                nums[i - 1] = nums[i];
            }
        }
        return cnt <= 1;
    }
}