【原】665. 非递减数列

文章目录

665. 非递减数列

这题在LeetCode中属于容易（原谅我一开始小看了），但还是被虐了 T^T

给你一个长度为 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

解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

解题思路

图解
有两种情况

1.nums[i] 比 nums[i-2] 大，让nums[i-1]=nums[i]

这种情况时，2后面是递增的，如果将 2 提升为3，可能会破坏后面数列的递增性，只能让 3 变成 2

像这样如果将3 变成 6 会破坏后面的递增性，只能讲6 变成 3

2.nums[i] 比 nums[i-2] 小，让nums[i] = nums[i-1]

但nums[i] 比 nums[i-2] 小的时候，如果不改 nums[i] 就只能去改nums[i-1] 和nums[i-2]，但是这样就会改两次，不符合题意，所以只能去改 nums[i] 来保证递增（无奈之举），如果后面还 不符合规则 就返回false 改不了了

代码

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                // nums[i] 比 nums[i-2] 大的时候  那么就让 nums[i-1]等于nums[i]就满足了 并且不会破坏后续列表与前面已经遍历处理过列表的可比性
                // nums[i] 比 nums[i-2] 小的时候  就必须让 nums[i]等于nums[i-1] 才能满足情况  否则是要调用两次
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
                count ++;
            }
        }
        return count <= 1;  
    }
};