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).
给定一个由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: 1、The n belongs to [1, 10,000].
Solutions: 这道题的解题思路并不复杂，但需要考虑到所有情况。我们先用一个计数器记录不满足条件的个数，当个数大于2的时候直接返回False。要使数组满足非降序的条件，只要修改不满足条件的数值对即可。但如何修改需要分情况讨论：第一种：[1,3,2,4]；第二种：[2,3,1,4]；第三种：[4,2,3,5]。所有不满足条件的数对都可以用这三种情况来表示并修改，这三种情况对应了下面代码的三种判断条件的修改方式。
Python (1) class Solution: def checkPossibility(self, nums): """ :type nums: List[int] :rtype: bool """ count = 0 for i in range(len(nums)-1): #用len(nums)-1是为了判断最后一个元素，避免列表的index溢出 if nums[i]>nums[i+1]: count += 1 if i == 0: nums[i] = nums[i+1] elif nums[i+1]>nums[i-1]: nums[i]= nums[i+1] else: nums[i+1] = nums[i] if count > 1: return False return True (2) #方法2是将原数组复制成两份，只要遇到不符合条件的情况时，要么修改i元素，要么修改i+1元素 #修改之后直接将数组排序，如果修改后的两个数组与排序后的数组都不同，那么直接返回False #只要两个数组中有一个符合条件就返回True class Solution(object): def checkPossibility(self, nums): """ :type nums: List[int] :rtype: bool """ one, two = nums[:], nums[:] for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: one[i] = nums[i + 1] two[i + 1] = nums[i] break return one == sorted(one) or two == sorted(two) C++ class Solution { public: bool checkPossibility(vector<int>& nums) { int count = 0; for (int i=0;i<nums.size()-1;i++){ if (nums[i]>nums[i+1]){ ++count; if (i == 0){ nums[i] = nums[i+1]; } else if (nums[i+1]>nums[i-1]){ nums[i] = nums[i+1]; } else{ nums[i+1] = nums[i]; } } if (count>1){ return false; } } return true; } };