665 Non-decreasing Array

665. Non-decreasing Array​
1. Question
Given an array withnintegers, your task is to check if it could become non-decreasing by modifyingat most1element.
We define an array is non-decreasing ifarray[i] <= array[i + 1]holds for everyi(1 <= i < n).
Example 1:
1
Input: [4,2,3]
2
​
3
Output: True
4
​
5
Explanation:
6
You could modify the first  4 to 1 to get a non-decreasing array.
Copied!
Example 2:
1
Input: [4,2,1]
2
​
3
Output: False
4
​
5
Explanation: You can't get a non-decreasing array by modify at most one element.
Copied!
Note:Thenbelongs to [1, 10,000].
2. Implementation
(1) DP (TLE)
Longest Increasing Subsequence的思想
1
class Solution {
2
    public boolean checkPossibility(int[] nums) {
3
        if (nums == null || nums.length <= 1) {
4
            return true;
5
        }
6
        int n = nums.length;
7
        int[] dp = new int[n];
8
        Arrays.fill(dp, 1);
9
​
10
        for (int i = 1; i < n; i++) {
11
            for (int j = 0; j < i; j++) {
12
                if (nums[j] <= nums[i] && (dp[j] + 1 > dp[i])) {
13
                    dp[i] = dp[j] + 1;
14
                }
15
            }
16
        }
17
​
18
        int maxLen = 1;
19
        for (int i = 0; i < n; i++) {
20
            maxLen = Math.max(maxLen, dp[i]);
21
        }
22
        return maxLen >= n - 1;
23
    }
24
}
Copied!
(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]
1
class Solution {
2
    public boolean checkPossibility(int[] nums) {
3
        if (nums == null || nums.length <= 1) {
4
            return true;
5
        }
6
​
7
        int n = nums.length;
8
        int count = 0;
9
        int prev = nums[0];
10
​
11
        for (int i = 1; i < n; i++) {
12
            if (nums[i] < prev) {
13
                ++count;
14
​
15
                if (count >= 2) {
16
                    return false;
17
                }
18
​
19
                if (i - 2 >= 0 && nums[i - 2] > nums[i]) continue;
20
​
21
            }
22
            prev = nums[i];
23
        }
24
        return true;
25
    }
26
}
Copied!
3. Time & Space Complexity
DP: 时间复杂度O(n^2), 空间复杂度O(n)
Greedy: 时间复杂度O(n^2), 空间复杂度O(n)

Google

400 Nth Digit

Last modified 2yr ago

Copy link

Contents

665. Non-decreasing Array

1. Question

2. Implementation

3. Time & Space Complexity

665. Non-decreasing Array​

1. Question

2. Implementation

3. Time & Space Complexity

665. Non-decreasing Array