题目描述
给定一个长度为 n
的整数数组,你的任务是判断在最多改变 1
个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n)
,满足 array[i] <= array[i + 1]
。
样例
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
注意
n
的范围为 [1, 10000]。
算法
(线性扫描) $O(n)$
- 用一个布尔变量保证出现递减的次数不超过一次。
- 从第二个数字开始检查前一个数字和自身的大小关系。在
nums[i] < nums[i - 1]
的情况下,若此时是第二次出现,则返回 false。若第一次出现,且nums[i - 2] > nums[i] && num[i - 1] > nums[i + 1]
(如果 i > 1 并且 i < n - 1),则返回 false,因为此时无法通过只改变nums[i]
或者nums[i - 1]
来保证递增关系。 - 最后返回 true 即可。
时间复杂度
- 线性扫描数组,故时间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int n = nums.size();
bool chance = true;
for (int i = 1; i < n; i++)
if (nums[i] < nums[i - 1]) {
if (!chance)
return false;
if (i > 1 && i < n - 1 && nums[i - 2] > nums[i] && nums[i - 1] > nums[i + 1])
return false;
chance = false;
}
return true;
}
};
大佬,分析里面第二点
nums[i - 1] < nums[i]
应该改为nums[i ] < nums[i - 1]
已修正~
且
nums[i - 2] > nums[i] && num[i - 1] > nums[i + 1]
(如果 i > 1 并且 i < n - 1)请问这是咋推出来的啊
出现
nums[i -1] > nums[i]
只要两种解决办法,一种是降低nums[i - 1]
,一种是增大nums[i]
,所以只需要通过构造出反例使得这两种都不可行就可以了。考虑3412
这四个数字,当前nums[i]
是1
,nums[i - 1]
是4
,此时没有办法只改变1
或只改变4
来做到整体递增。可以参考下面的人写的评论。
太棒了,多谢指点
理解一哈这个代码。 比如4 5 3 4,检测到3<5使得序列不是非递减。那么现在是否可以补救呢?若之前已经用过补救机会,那就是第二次,直接失败。否则可以补救。
那么如何补救呢?要么让3变大,要么让5变小。然后我们检测这两种方式都不行所以返回false。为什么不行呢?让3变大,至少变成5这么大,可这样它就比后面的4还大了。5变小至少要变成3那么小,这样它又比之前的4还小了。所以这两种办法都不行,返回false。
nice
赞!!写得不错!!