秋高斋

665. 非递减数列

发表于 更新于 分类于
本文字数： 889 阅读时长 ≈ 1 分钟
修改哪个元素，才是问题的难点

leetcode-65. 非递减数列

这段代码实现了一个时间复杂度为 O(n)、空间复杂度为 O(1) 的解法，用于判断在最多修改一个元素的情况下，给定的数组 nums 能否变成一个非递减数列。

具体来说，它通过遍历数组 nums，对于每一对相邻元素 (x, y) 进行比较，如果 x > y，则说明需要修改一个元素才能满足非递减的条件。此时，将修改次数 cnt 加一，并判断 cnt 是否超过了一次，如果超过了一次，则说明无法只修改一个元素来满足条件，直接返回 false。

如果 cnt 不超过一次，则需要考虑修改哪个元素。为了保证修改后的数组满足非递减的条件，有两种可能的情况需要考虑：

  1. 修改 nums[i]，使得 x <= y，此时修改后的数组可能会影响到 i - 1 和 i + 1 位置的元素。如果 nums[i + 1] < nums[i - 1]，则说明需要将 nums[i + 1] 修改为 nums[i]，否则将 nums[i] 修改为 nums[i + 1]。

  2. 修改 nums[i + 1]，使得 x <= y，此时只会影响到 i + 1 位置的元素，因为 i 和 i - 1 位置的元素已经是非递减的了。因此，直接将 nums[i + 1] 修改为 nums[i] 即可。

最后，如果遍历完整个数组 nums 之后都没有返回 false，则说明只需要修改不超过一次元素就可以将数组变成非递减的，返回 true 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool checkPossibility(vector<int> &nums) {
        int n = nums.size(), cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                cnt++;
                if (cnt > 1) {
                    return false;
                }
                if (i > 0 && y < nums[i - 1]) {
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }
};