665. Non-decreasing Array

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one 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.

Constraints:

• n == nums.length
• $1 <= n <= 10^4$
• $-10^5 <= nums[i] <= 10^5$

Code

例子

• 4, (2), 3
• -1, 4, (2), 3
• 2, 3, 3, (2), 4

当后面的数字小于前面的数字时需要修改. 但是, 有时候需要修改较大的数字(例 1,2), 有时候要修改较小的那个数字(例 3)，

1. 如果再前面的数不存在(例 1): 4 前面没有数字了, 那么直接修改前面的数字为当前的数字 2 即可
2. 如果再前面的数字存在, 并且小于当前数(例 2): -1 小于 2, 那么需要修改前面的数字 4 为当前数字 2
3. 如果再前面的数大于当前数(例 3): 3 大于 2,那么需要修改当前数 2 为前面的数 3

class Solution {
    public boolean checkPossibility(int[] nums) {
        boolean modified = false;

        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[i - 1]) {
                if (modified) return false;
                modified = true;

                // 例1, 2
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    // -1, 4, 2, 1
                    // nums[i - 1] = nums[i];
                    continue;
                } else {
                    // 例3
                    // 3, 4, 2, 3
                    nums[i] = nums[i - 1];
                }
            }
        }

        return true;
    }
}