题目
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).
Example 1:
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
题意
判断已给数组是否最多修改一次能否构成非递减数组。
题解
如果出现array[i] < array[i - 1] 1.要么修改array[i] 2.要么修改array[i-1] 如果判断是1还是2 执行1：当a[i+1] >= a[i-1] 执行2：当a[i] >= a[i-2]
python代码
class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
"""
如果array[i] < array[i - 1]
1.要么修改array[i]
2.要么修改array[i-1]
如果判断是1还是2
执行1：当a[i+1] >= a[i-1]
执行2：当a[i] >= a[i-2]
"""
modify =
0
index =
0
for i
in range(
1, len(nums)):
if nums[i] < nums[i-
1]:
index = i
modify = modify +
1
if modify ==
0:
return True
elif modify >
1:
return False
else:
if index==
1 or index==len(nums)-
1 or nums[index+
1]>=nums[index-
1]
or nums[index]>=nums[index-
2]:
return True
else:
return False
C++代码
class Solution {
public:
bool checkPossibility(
vector<int>& nums) {
int modify =
0, index =
0, i;
for(
int i=
1; i<nums.size(); i++)
{
if(nums[i] < nums[i-
1])
{
index = i;
modify++;
}
}
if(modify ==
0){
return true;
}
if(modify >
1){
return false;
}
if(index==
1||index==nums.size()-
1||nums[index+
1]>=nums[index-
1]||nums[index]>=nums[index-
2]){
return true;
}
return false;
}
};
