# Non-decreasing Array

Posted by chunyang on April 5, 2019

### 题目

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

### 解法

#### 思路

a = nums[i-1]

b = nums[i]

c = nums[i+1]

d = nums[i+2]

• a <= d
• b>=a && b <=d or `c>=a && c<=d

#### 代码

class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int start = 0;
int end = nums.size();
int reversal = 0;
int a, b, c, d;
a = INT_MIN;
d = INT_MAX;
while (start < end - 1) {
if (nums[start] > nums[start+1]) {
if (reversal != 0) {
return false;
}
reversal += 1;
b = nums[start];
c = nums[start+1];
if (start > 0) a = nums[start - 1];
if (start + 2 < end) d = nums[start+2];
bool bb = b >= a && b <= d;
bool cc = c >= a && c <= d;
if (!(bb || cc)) {
return false;
}

}
++start;
}
return true;
// cout << a << " " << b << " " << c <<  " " << d << endl;
}
};