内容
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。
示例 1:
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明: n 的范围为 [1, 10,000]。
思路
既然是要做成一个非递减数列,那么就是 i1<=i2<=i3
如果不满足的话,那就需要分情况讨论,以下是不满足的所有组合:
- i1>i2<=i3
这种情况直接让i1=i2即可,
因为不管i1>i3还是i1<i3只要满足i1<=i2即可
2、 i1>i2>i3
这种情况无解
3、 i1<=i2>i3
假设有i1<=i2>i3<=i4
然后这里可能需要分两种情况:
1. 如果i1<i3,同时i3需要>=i2,也就是i1<=i2<=i3<=i4,然而事实是i3<i2,如果将i3=i2,那么i3会比之前变大,很可能会出现i3>i4的情况,所以这里只能选择将i2变小,因为i3也大于i1,所以i2变成i3还是能满足i2>=i1的条件。
2. 如果i1>i3,那么i3也要满足>=i2,所以这里只能i3=i2
代码
/**
* @param {number[]} nums
* @return {boolean}
*/
var checkPossibility = function (nums) {
var changeCount = 0;
for (var i = 0; i < nums.length; i++) {
var last = nums[i - 1] || -(Math.pow(2, 31) + 100);
var next = nums[i + 1] || Math.pow(2, 31) + 100;
if (last <= nums[i] && nums[i] > next) {
if (changeCount > 0) return false;
if (last < next) {
nums[i] = next;
} else {
nums[i + 1] = nums[i];
}
changeCount++;
i = -1;
}
if (last > nums[i] && nums[i] > next) {
return false;
}
if (last > nums[i] && nums[i] <= next) {
if (changeCount > 0) return false;
nums[i] = last;
changeCount++;
i = -1;
}
}
return true;
};
网友评论