每天一道leetcode665-非递减数列

665_(非递减数列)Non-decreasing Array

1 问题描述、输入输出与样例

1.1 问题描述

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。 我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。 说明: n 的范围为 [1, 10,000]。

1.2 输入与输出

输入：

• vector & nums:输入的整数数组

输出：

• bool:在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列

1.3 样例

1.3.1 样例1

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

1.3.2 样例2

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

2 思路描述与代码

2.1 思路描述（比较计数法）

cnt统计当前数比前一个数小的个数; 遍历数组中所有的值

• 如果当前值比前一个值小
  • 如果cnt == 1，则判断是否存在纠正的方式，无则返回false
  • 否则cnt >= 2，则不存在纠正方式，返回false

2.2 代码

bool checkPossibility(vector<int>& nums) {
    int n = nums.size();
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (nums[i - 1] > nums[i]) {
            cnt++;
            //cnt = 1时，需要注意有两种情况可以补救：
            //1. 比如[-1 4 2 3], 4 < 2, 2 > -1, 通过修改 4  为 -1~2 间的数都可以补救
            //2. 比如[1 2 -1 3],-1 < 2, 2 < 3,  通过修改 -1 为  2~3 间的数都可以补救

            //cnt >= 2则怎样都不行了，因为只能修改一次
            if((cnt == 1 && i >= 2 && i < n - 1 && nums[i] < nums[i - 2] && nums[i + 1] < nums[i - 1]) || cnt >= 2) return false;
        }
    }
    return true;
}

3 思考与拓展

3.1 思考

本题中需要考虑多种情况的可能性，否则容易犯错。

3.1.1 其他方法

无。

3.1.2 复杂度分析

3.1.3 难点分析

1. 当前值比前一个值小只出现一次时需要考虑[-1 4 2 3]、[1 2 -1 3]、[1,2,3,2]、[4,1,2,3]之类可纠正的情况

3.2 拓展

如果给你的是链表数据呢？