题目描述

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

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

示例 1:

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

示例 2:

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

提示：

  • 1 <= n <= 10 ^ 4
  • 10 ^ 5 <= nums[i] <= 10 ^ 5

解法

这道题目，就是去找到数组中不满足非递减序列元素的个数，如果个数大于1，则返回false，否则返回true。

但是有一个地方需要注意，nums[i] > nums[i + 1]有两种情况，一种是nums[i + 1] > nums[i - 1]，这种情况可以把nums[i]变为nums[i + 1]，无需考虑，可以继续遍历；

另外一种情况是nums[i + 1] < nums[i - 1]，这个时候就需要调整nums[i + 1]为nums[i]， 由于nums[i + 1]还需要和后续的结果做比较，所以要进行赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool IsNonDecreasing(vector<int>& nums) {
    int cnt = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        if (nums[i] > nums[i +1]) {
            cnt++;
            if (cnt > 1) {
                return false;
            }
            if (i > 0 && nums[i + 1] < nums[i - 1]) {
                nums[i +1] = nums[i]
            }
        }
    }
    return true;
}