665.non-decreasing Array

665.non-decreasing Arrar

原题

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).

Example1
1
2
3
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example2
1
2
3
Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

讲解

该题给我们任意一个数组,并允许我们只修改其中一个数字,使其变成一个非递减的数组。如果可以返回true,否则返回false。
解题思路在于当nums[i]\<nums[i-1]时如何更改数字。当num[i-1]前面的数字不存在或者同时也小于nums[i]时,这时将nums[i-1]值改为nums[i]。否则将nums[i]值改为nums[i-1].由于我们只有一次修改机会,设置变量chance为1,修改完成后自减,下次如需再次修改则无法成功返回false。一下为源码。

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {number[]} nums
* @return {boolean}
*/
var checkPossibility = function(nums) {
var chance=1;
for(var i=1;i<nums.length;i++){
if(nums[i]<nums[i-1]){
if(chance==0){
return false;
}else{
if(i-2<0||nums[i-2]<nums[i]){
nums[i-1]=nums[i];
}else{
nums[i]=nums[i-1];
}
chance--;
}
}
}
return true;
};