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:

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:Thenbelongs to [1, 10,000].

2. Implementation

(1) DP (TLE)

Longest Increasing Subsequence的思想

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]

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)