Leetcode（665）——非递减数列

题目

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

提示：

• n == nums.length
• 1 <= n <= 104
• -105 <= nums[i] <= 105

题解

方法一：贪心算法

思路

​​  首先思考如下问题：要使数组 $\text{nums}$ 变成一个非递减数列，数组中最多有多少个 $i$ 满足 $\text{nums}[i]>\text{nums}[i+1]$？

最多一个。

​​  假设有两个不同的下标 $i$, $j$ 满足上述不等式，不妨设 $i<j$。

1. 若 $i+1<j$，则无论怎么修改 $\text{nums}[i]$ 或 $\text{nums}[i+1]$，都不会影响 $\text{nums}[j]$ 与 $\text{nums}[j+1]$ 之间的大小关系；修改 $\text{nums}[j]$ 或 $\text{nums}[j+1]$ 也同理。因此，这种情况下，我们无法将 $\text{nums}$ 变成非递减数列。
2. 若 $i+1=j$，则有 $\text{nums}[i]>\text{nums}[i+1]>\text{nums}[i+2]$。同样地，无论怎么修改其中一个数，都无法使这三个数变为 $\text{nums}[i]\le \text{nums}[i+1]\le \text{nums}[i+2]$ 的大小关系。

​​  满足这个条件就足够了吗？并不，对于满足该条件的数组 $[3,4,1,2]$ 而言，无论怎么修改也无法将其变成非递减数列。
​​  因此，若找到了一个满足 $\text{nums}[i]>\text{nums}[i+1]$ 的 $i$，在修改 $\text{nums}[i]$ 或 $\text{nums}[i+1]$ 之后，还需要检查 $\text{nums}$ 是否变成了非递减数列。

​​  我们可以将 $\text{nums}[i]$ 修改成小于或等于 $\text{nums}[i+1]$ 的数，但由于还需要保证 $\text{nums}[i]$ 不小于它之前的数，$\text{nums}[i]$ 越大越好，所以将 $\text{nums}[i]$ 修改成 $\text{nums}[i+1]$ 是最佳的；同理，对于 $\text{nums}[i+1]$，修改成 $\text{nums}[i]$ 是最佳的。

能否只遍历一次遍历 $\text{nums}$ 数组呢？
​​  修改 $\text{nums}[i]$ 为 $\text{nums}[i+1]$ 后，还需要保证 $\text{nums}[i-1]\le \text{nums}[i]$ 仍然成立，即 $\text{nums}[i-1]\le \text{nums}[i+1]$，若该不等式不成立则整个数组必然不是非递减的，则需要修改 $\text{nums}[i+1]$ 为 $\text{nums}[i]$。修改完后，接着判断后续数字的大小关系。在遍历中统计 $\text{nums}[i]>\text{nums}[i+1]$ 的次数，若超过一次可以直接返回 $\text{false}$。

代码实现

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        // 1.找到第一对导致序列为非递减的两个值（前者大于后者），找不到则返回true
        // 2.找到第一对导致序列为非递减的两个值,判断第一个值的前者是否小于等于第二个值,若为true则继续,若为false则
        // 判断第一个值是否小于等于第二个值的后者,若为true则继续，否则返回false
        // 3.再判断后序列是否都为非递减数列，即能否找到第二对导致序列为非递减的两个值，找到返回false，否则返回true
        int size = nums.size(), non_value = 0;  // non_value 表示导致序列为非递减地方的个数
        if(size <= 2) return true;  // 若小于等于2，则一定可以在最多改变1个元素的情况下使得该数组变成一个非递减数列
        for(int n = 1; n < size; n++){
            if(nums[n-1] > nums[n]){
                // 非递减的两个值
                if(++non_value <= 1) {
                    // 还要注意是否是 n-1 是否是第一个值和 n 是否是最后一个值的特殊情况
                    if(n == 1 || nums[n-2] <= nums[n] || n == size-1 || nums[n-1] <= nums[n+1]) continue;
                    else return false;
                }else return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。
空间复杂度：$O(1)$