> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/non-decreasing-array.md).

# 665. Non-decreasing Array

https\://leetcode.com/problems/non-decreasing-array/description/

Given an array `nums` 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 `nums[i] <= nums[i + 1]` holds for every `i` (0-based) such that `(0 <= i <= n - 2)`.

**Example 1:**

```
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
```

**Example 2:**

```
Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.
```

## Thoughts

问给定数组在至多只改变一个数的条件下能否满足非严格单调递增。在出现不满足非严格递增nums\[i]和nums\[i+1]时，由于只能改一个，被改的元素只能从它俩中选。当nums\[i + 1]比nums\[i -1]还小时，只能通过修改nums\[i+1]来满足『至多一个』的条件。改完后继续遍历，当再次出现不满足非严格递增时返回False。

![](https://2251957238-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LcOoIFG2VRxGaJDySQN%2F-LcOoJHd7TzQh5w1SKcJ%2F-LcOopYUIoYbsUkKKVFj%2Fimport_non_dec.png?generation=1555211457115528\&alt=media)

## Code

```python
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        found = False
        for i in range(0, len(nums) - 1):
            if nums[i] <= nums[i + 1]: continue
            if found: return False
            found = True
            if i > 0 and nums[i - 1] > nums[i + 1]: nums[i + 1] = nums[i]
        return True
    
```

```java
class Solution {
    public boolean checkPossibility(int[] nums) {
        for (int i = 0, count = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (count == 1) {
                    return false;
                }
                if (i > 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                }
                count++;
            }
        }
        return true;
    }
}
```

## Analysis

时间复杂度O(N).

## Ver.2

不修改原数组版本。

```
class Solution {
    public boolean checkPossibility(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        for (int i = 0, cur = nums[0], count = 0; i < nums.length - 1; i++) {
            if (cur > nums[i + 1]) {
                if (count == 1) {
                    return false;
                }
                if (!(i > 0 && nums[i - 1] > nums[i + 1])) {
                    cur = nums[i + 1];
                }
                count++;
            } else {
                cur = nums[i + 1];
            }
        }
        return true;
    }
}
```