leetcode665. 非递减数列

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

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

示例 1:

输入: [4,2,3]

输出: True

解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

输入: [4,2,1]

输出: False

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

思路：这个题分为两种情况来看，第一种：如果最开头的两个数，后面的数比前面的数要小，那就直接将后面的数赋给前面那个数，然后改变了一个元素，标志位flag为0，后面如果找到后面的元素又比前面元素小的话就返回false，第二种，就是这两个数并不是开头的两个数，这时候就需要判断后面的数是不是比前面数的前一个数大，如果满足就将后一个数赋给前一个数，同理标志位应该减为0.

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int flag = 1, nCount = nums.size();
        for (int i = 1; i < nCount; ++i) 
        {
            if (nums[i] < nums[i - 1]) 
            {
                if (flag == 0) 
                    return false;
                if (i == 1 || nums[i] >= nums[i - 2]) 
                    nums[i - 1] = nums[i];
                else 
                    nums[i] = nums[i - 1];
                flag--;
            } 
        }
        return true;
    }
};