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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

思路

还没见到更好的思路