內(nèi)容
給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組猎贴，你的任務(wù)是判斷在最多改變 1 個(gè)元素的情況下弃酌，該數(shù)組能否變成一個(gè)非遞減數(shù)列犬第。
我們是這樣定義一個(gè)非遞減數(shù)列的： 對(duì)于數(shù)組中所有的 i (1 <= i < n)荸哟，滿足 array[i] <= array[i + 1]。
示例 1:
輸入: [4,2,3]
輸出: True
解釋: 你可以通過(guò)把第一個(gè)4變成1來(lái)使得它成為一個(gè)非遞減數(shù)列瞬捕。
示例 2:
輸入: [4,2,1]
輸出: False
解釋: 你不能在只改變一個(gè)元素的情況下將其變?yōu)榉沁f減數(shù)列鞍历。
說(shuō)明: n 的范圍為 [1, 10,000]。
思路
既然是要做成一個(gè)非遞減數(shù)列肪虎，那么就是 i1<=i2<=i3
如果不滿足的話劣砍，那就需要分情況討論，以下是不滿足的所有組合：
- i1>i2<=i3
這種情況直接讓i1=i2即可扇救，
因?yàn)椴还躨1>i3還是i1<i3只要滿足i1<=i2即可
2刑枝、 i1>i2>i3
這種情況無(wú)解
3、 i1<=i2>i3
假設(shè)有i1<=i2>i3<=i4
然后這里可能需要分兩種情況:
1. 如果i1<i3迅腔，同時(shí)i3需要>=i2装畅，也就是i1<=i2<=i3<=i4，然而事實(shí)是i3<i2沧烈，如果將i3=i2掠兄，那么i3會(huì)比之前變大，很可能會(huì)出現(xiàn)i3>i4的情況锌雀，所以這里只能選擇將i2變小蚂夕，因?yàn)閕3也大于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;
};
