non-decreasing-array

Non-decreasing Array – LeetCode 665

Problem

Description

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

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Answer

Original

Code

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int cnt = 1, n = nums.size();
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[i - 1]) {
                if (cnt == 0) return false;
                if (i == 1 || nums[i] >= nums[i - 2]) nums[i - 1] = nums[i];
                else nums[i] = nums[i - 1];
                --cnt;
            } 
        }
        return true;
    }
};

思路

针对具体情况分类讨论。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$24$ ms，排名$5.91\%$

Better

思路

还没见到更好的思路