665. Non-decreasing Array

https://leetcode.com/problems/non-decreasing-array/description/

Given an array nums 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 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.

Thoughts

问给定数组在至多只改变一个数的条件下能否满足非严格单调递增。在出现不满足非严格递增nums[i]和nums[i+1]时，由于只能改一个，被改的元素只能从它俩中选。当nums[i + 1]比nums[i -1]还小时，只能通过修改nums[i+1]来满足『至多一个』的条件。改完后继续遍历，当再次出现不满足非严格递增时返回False。

Code

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        found = False
        for i in range(0, len(nums) - 1):
            if nums[i] <= nums[i + 1]: continue
            if found: return False
            found = True
            if i > 0 and nums[i - 1] > nums[i + 1]: nums[i + 1] = nums[i]
        return True
    

class Solution {
    public boolean checkPossibility(int[] nums) {
        for (int i = 0, count = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (count == 1) {
                    return false;
                }
                if (i > 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                }
                count++;
            }
        }
        return true;
    }
}

Analysis

时间复杂度O(N).

Ver.2

不修改原数组版本。

class Solution {
    public boolean checkPossibility(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        for (int i = 0, cur = nums[0], count = 0; i < nums.length - 1; i++) {
            if (cur > nums[i + 1]) {
                if (count == 1) {
                    return false;
                }
                if (!(i > 0 && nums[i - 1] > nums[i + 1])) {
                    cur = nums[i + 1];
                }
                count++;
            } else {
                cur = nums[i + 1];
            }
        }
        return true;
    }
}