Title

the problem link

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

题目大意：判断一个数组修改一次是否可以改为有序的

Solution

记录非有序的位置，然后修改这位置旁边的，修改为有序的

//cpp:
class Solution {
public:
	bool checkPossibility(vector<int>& nums) {
		int modified = 0;
		for (int i = 1; i < nums.size(); i++) {
			if (nums[i] < nums[i - 1]) {
				if (modified > 0)
					return false;
				modified++;

				if (i - 2 >=0 &&nums[i - 2] <= nums[i]||i-1==0) {
					nums[i - 1] = nums[i];
				}
				else {
					nums[i] = nums[i - 1];
				}
			}
		}
		return true;
	}
};