每日一题-1st

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

Leetcode 665. 非递减序列

题干

给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 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
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

本人错误思路

遍历法：（O(n)时间、O(1)空间）：仅允许至多一处num[i+1] - num[i] < 0，否则跳出循环；

评价：错误。因为可能虽然趋势是先升再降再升，但后面的数据小于前面的就不行，例如：[3,4,2,3]

遍历法+前后判断：在遍历法基础上，一旦找到第一个不符合规则的元素，立即检查该元素的前后是否能满足递增要求；

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int former = -1e5, latter = 0, len = nums.size();
        bool signal = 0;
        for (int i = 0; i < len; ++i) {
            latter = nums[i];
            if (latter - former < 0) {
                if (signal) return false;
                else {
                    if (i + 1 < len && nums[i + 1] < former) return false;
                    else signal = 1;
                }
            }
            former = latter;
        }
        return true;
    }
};

评价：错误。因为例子[2,4,2,3]，只考虑检查到的第一个元素（这里是第二个2）两端是不行的。改动的元素也可以是出现异常元素的前一个（这里是4）；

取差比较：如果这是一个异常位，且发现相邻两数的差的序列（累减生成序列）的相邻两项和小于零，说明位于异常位两端的数据一定不呈非递减关系；

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int formerS = nums[0], latterS = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            latterS = nums[i] - nums[i - 1];
            // formerS + latterS = num[i + 1] - num[i - 1]
            if (formerS + latterS < 0) return false;
            formerS = latterS;
        }
        return true;
    }
};

评价：错误。累减生成序列只考虑到间隔一个元素的两元素，没有考虑出现多次非递减情况，如[4,-5,5,-2,6]，实际不行，按此法却是行的；

间隔比较：由取差比较的原理可知，只需比较相隔一个元素的两元素是否符合规定；

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int len = nums.size();
        // When its length <= 2, it is in to be true.
        if (len <= 2) return true;
        bool flag = 1;
        for (int i = 0; i < len - 1; ++i) {
            // Non-increasing point detected.
            if (nums[i + 1] - nums[i] < 0) {
                // Has it happened before?
                // No.
                if (flag) {
                    // Considering that if we change nums[i],
                    // can num[i-1] & num[i+1] meet the need?
                    if (i > 0 && nums[i + 1] < nums[i - 1]) return false;
                    // Assuming that num[i] is changed. We can't do it again.
                    else flag = 0;
                }
                   // Yes.
                else return false;
            }
        }
        return true;
    }
};

评价：错误。因为例子[5,7,1,8]。

思路整理

通过以上分析发现，如果开始发现不满足非递减定义的相邻元素，例如：$a_i>a_{i+1}$，则应该想到既可以通过更换$a_i$（例子[2,4,2,3]），也可以通过更换$a_{i+1}$（例子[5,7,1,8]）来完成；

进一步分析，考虑length > 3的情况，如果在 $[…, a_{i-1},a_i,a_{i+1},a_{i+2},…]$ 中发现 $a_i\gt a_{i+1}$ ，先检查直接有无改动，有则返回false；无则考虑2种修改方案：1、修改$a_i$，要求$a_{i-1}$和$a_{i+1}$组成非递减序列；2、修改$a_{i+1}$，要求$a_i$和$a_{i+2}$组成非递减序列。这两种方法都不满足者，只能返回false。

如果错误在开头：$[a_0,a_1,a_2,…]$ 有 $a_0\gt a_1$，则如果更改$a_0$，那么一定可以改；如果更改$a_1$，那么要求$a_0$和$a_2$构成非递减序列（结尾同理）；

现在就假定我们总是以修改 $a_{i}$ 优先，如果不满足$a_{i-1}$和$a_{i+1}$组成非递减序列，再换成修改$a_{i+1}$（在开头就不用判断可行性）.

length = 3无需特殊考虑。

最终解答

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        bool isPatched = 0;
        int len = nums.size();
        for (int i = 0; i < len - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                if (isPatched) return false;
                isPatched = 1;
                // 既不能更改ai，也不能更改ai+1
                if (!(!i || i > 0 && nums[i - 1] <= nums[i + 1])
                    && !(i == len - 2 || i < len - 2 && nums[i] <= nums[i + 2]))
                    return false;
            }
        }
        return true;
    }
};

如果想提高代码判断效率（也没法再提升一个数量级，不过对小样本会有提升），考虑到其实真正需要判断 “既不能更改 $a_i$，也不能更改 $a_{i+1}$” 的只有一个逆序的位置，因为多于一个就会返回false。

所以可以先记下逆序的位置，最后判断一遍就行，如下：

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        bool isPatched = 0;
        int len = nums.size(), err = 0;
        for (int i = 0; i < len - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                if (isPatched) return false;
                isPatched = 1; err = i;
            }
        }
        // 只有一处逆序，且在开头和末尾，都是不用判断，直接是true
        if (err > 0 && err < len - 2)
            // 既不能更改ai，也不能更改ai+1
            if (nums[err - 1] > nums[err + 1] && nums[err] > nums[err + 2])
                return false;
        return true;
    }
};