题目链接

665. 非递减数列 - 力扣（LeetCode）

题目描述

给定数组nums[i]，判断能否在最多改变一个数组的情况下，使得该数组变为非递减序列？

输入输出样例

1
2
3
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

题目解释

考虑下坡的状况，移动峰值点，可以将下坡变为平缓

代码

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/non-decreasing-array/solutions/594758/fei-di-jian-shu-lie-by-leetcode-solution-zdsm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        // 定义下坡的数量
        int down = 0;
        int length = nums.size();
        for (int i = 1; i < length; i++) {
            int x = nums[i - 1], y = nums[i];

            if (x > y) {
                // 修改之后判断是不是有序数组
                nums[i - 1] = nums[i];
                if (is_sorted(nums.begin(), nums.end())) {
                    return true;
                }
                nums[i - 1] = x;
                nums[i] = nums[i - 1];
                return is_sorted(nums.begin(), nums.end());
            }
        }
        return true;
    }
};


class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        // 定义下坡的数量
        int cnt = 0;
        int length = nums.size();
        for (int i = 0; i < length - 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;
    }
};