Leetcode 665. 非递减数列【C++】

地址：https://leetcode-cn.com/problems/non-decreasing-array/

题目

给你一个长度为 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 <= n <= 10 ^ 4
• 10 ^ 5 <= nums[i] <= 10 ^ 5

解题思路

自己做没想出来好的方法，最后看了官方题解~

思路就是找 nums[i] > nums[i + 1] 出现的次数，但需要注意 nums[i + 1] < nums[i - 1] 的情况，例如一组数 3, 4, 2 ，此时 4 > 2 ，默认我们认为 4 是需要修改的数，应将其修改为 <=2 的数，但如果这么做就会发现修改后 3 大于后续的两个数，不符合非递减的要求，所以正确的操作是将后一个数 2 修改为 >=4 的数，保险的做法正是将其修改为 4 。

继续往后遍历查找 nums[i] > nums[i + 1] 的情况，如果第二次发现这样的情况则说明通过一次修改不能使该数组成为非递减数列，直接返回 false ，否则遍历结束后返回默认值 true 。

代码

class Solution {
public:
    bool checkPossibility(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;
    }
};