Leetcode 665. 非递减数列

原题链接：Leetcode 665. Non-decreasing Array

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]
Output: true

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false

Explanation: You cannot get a non-decreasing array by modifying at most one element.

Constraints:

• n == nums.length
• 1 <= n <= 10⁴
• -10⁵ <= nums[i] <= 10⁵

题目大意：

给了一个有n个元素的数组nums，问能否仅改变一个元素一次，使得序列变成非递减序列

方法一：遍历

思路：

原先我认为只要判断比前一个元素小的元素个数即可，也过了样例，但还是错了。像[3, 4, 2, 3] 就满足只有一个元素比前一个元素小，无法通过一次调整变为非递减序列。

当nums[i] < nums[i - 1]时，主要可以分为三种情况：

1. 例如[4, 2, 5] ， 此时i = 1, 可以将4 调小，也可以将 2调到4或者5
2. 例如1, 4, 2, 5，此时i > 1，可以将4调小，也可以将2调大
3. 例如3, 4, 2, 5，此时nums[i] >= nums[i - 2]，只能将2调大

C++ 代码：

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;  // 调整次数
        for(int i = 1; i < nums.size(); i++ ){
            if(nums[i] < nums[i - 1]){  // 出现了破坏非递减的元素
                if(i == 1 || nums[i] >= nums[i - 2]){ 
                    nums[i - 1] = nums[i];
                }
                else{
                    nums[i] = nums[i - 1];
                }
                count++;
            }
        }

        return count <= 1;  // 判断调整次数是否超过1次
    }
};

复杂度分析：

• 时间复杂度：O(n)，遍历一遍数组
• 空间复杂度：O(1)