# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/google/665-non-decreasing-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.