非递减数列

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

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

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

题解:

假设有两个不同的下标 ii, jj 满足上述不等式,不妨设 i<ji<j.

若 i+1<j,则无论怎么修改nums[i] 或nums[i+1],都不会影响 nums[j] 与 nums[j+1] 之间的大小关系;修改 nums[j] 或 nums[j+1] 也同理。因此,这种情况下,我们无法将 nums 变成非递减数列。

若 i+1=j,则有nums[i]>nums[i+1]>nums[i+2]同样地,无论怎么修改其中一个数,都无法使这三个数变为nums[i]≤nums[i+1]≤nums[i+2] 的大小关系。

满足这个条件就足够了吗?并不,对于满足该条件的数组 [3,4,1,2]而言,无论怎么修改也无法将其变成非递减数列。

因此,若找到了一个满足nums[i]>nums[i+1]的 i,在修改nums[i] 或 nums[i+1] 之后,还需要检查 nums 是否变成了非递减数列。

我们可以将nums[i] 修改成小于或等于nums[i+1] 的数,但由于还需要保证 nums[i] 不小于它之前的数,nums[i] 越大越好,所以将 nums[i] 修改成 nums[i+1] 是最佳的;同理,对于 nums[i+1],修改成nums[i] 是最佳的。

修改nums[i] 为 nums[i+1] 后,还需要保证 nums[i−1]≤nums[i] 仍然成立,即 nums[i−1]≤nums[i+1],若该不等式不成立则整个数组必然不是非递减的,则需要修改 nums[i+1] 为 nums[i]。修改完后,接着判断后续数字的大小关系。在遍历中统计 nums[i]>nums[i+1] 的次数,若超过一次可以直接返回false。


func checkPossibility(nums []int) bool {
    count := 0
    for i:=0;i<len(nums)-1;i++{
        x, y := nums[i], nums[i+1]
        if x > y {
            count++
            if count > 1 {
                return false
            }
            if i > 0 && y < nums[i-1] {
                nums[i+1] = x
            }
        }
    }
    return true
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注