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

# 665 Non-decreasing Array

## 665. [Non-decreasing Array](https://leetcode.com/problems/non-decreasing-array/description/)

## 1. Question

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:**&#x54;he`n`belongs to \[1, 10,000].

## 2. Implementation

**(1) DP (TLE)**

Longest Increasing Subsequence的思想

```java
class Solution {
    public boolean checkPossibility(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i] && (dp[j] + 1 > dp[i])) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen >= n - 1;
    }
}
```

**(2) Greedy**

思路: 要使得整个数组是非递减，我们用一个prev变量记录**在nums\[i]之前的最大数**，用count记录递减的次数，显然当count大于等于2时，我们无法修改一次数组使其递增。如果nums\[i] < prev, 这里有两种情况决定如何更新prev:

1.如果nums\[i - 2]不存在或者nums\[i - 2] > nums\[i]时，由于nums\[i] < prev已经出现一次递减情况, 为了避免再出现一次递减，保证nums在\[i -2, i]的非递减性, 我们不更新prev, 这等价于将nums\[i]变成prev

2.如果nums\[i - 2] <= nums\[i]，为了保证nums\[i - 2, i]的非递减性, 我们将prev更新为nums\[i]

```java
class Solution {
    public boolean checkPossibility(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }

        int n = nums.length;
        int count = 0;
        int prev = nums[0];

        for (int i = 1; i < n; i++) {
            if (nums[i] < prev) {
                ++count;

                if (count >= 2) {
                    return false;
                }

                if (i - 2 >= 0 && nums[i - 2] > nums[i]) continue;

            }
            prev = nums[i];
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

**DP**: 时间复杂度O(n^2), 空间复杂度O(n)

**Greedy:** 时间复杂度O(n^2), 空间复杂度O(n)