Cinte's Leetcode Record
0%

665. 非递减数列

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

665. 非递减数列

所有纠正只在转折处出现

两种情况

1639223566766.jpg 这种情况下把nums[i-1]改成比nums[i-2]和nums[i]之前的值即可

1639223632869.jpg 这种情况下把nums[i]改成nums[i-1]和nums[i+1]之间的值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int n = nums.size();
        bool isCorrect = false;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] < nums[i - 1])
            {
                if(isCorrect)
                    return false;
                if(i == 1 || ( i >= 2 && nums[i] >= nums[i - 2]))
                    isCorrect = true;
                else if(i == n - 1 || (i < n - 1 && nums[i + 1] >= nums[i - 1]))
                    isCorrect = true;
                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
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        bool isC = false;
        for(int i = 0, n = nums.size(); i < n - 1; ++i)
        {
            if(nums[i] > nums[i + 1])
            {
                if(isC)
                    return false;
                // 当nums[i+1]>=nums[i-1]的时候，只需要让nums[i]=nums[i+1]或者nums[i+1]=nums[i],则无论如何都能成立,所以这里不动的话对后面没有影响
                // 但是nums[i+1]<nums[i-1],如果令nums[i]=nums[i+1],必然不成立，所以需要让nums[i+1]=nums[i]
                if(i != 0 && nums[i + 1] < nums[i - 1])
                    nums[i + 1] = nums[i];
                isC = true;
            }
        }
        return true;
    }
};