Leetcode 665. Non-decreasing Array

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Non-decreasing Array

2. Solution

解析：Version 1首先对前后相邻的两个值进行比较，统计当前值nums[i]大于后值num[i+1]的次数，并保存当前值的索引index，如果一次没出现，说明当前数组为非递减数组，如果大于两次，只修改一个值的情况下不可能变为非递减数组。当只出现一次时，需要具体分析相关情况。当nums[index]位于数组第一个(0)或倒数第二(len(nums) - 2)的位置时，此时修改nums[index]即可满足非递减数组。当nums[index - 1] <= nums[index + 1]时，修改nums[index]可满足非递减数组。当nums[index] <= nums[index + 2]时，修改nums[index+1]可满足非递减数组。除此之外，无论是修改nums[index]还是nums[index+1]都不能变为非递减数组。

• Version 1

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0
        index = 0
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                count += 1
                index = i
        if count == 0:
            return True
        elif count > 1:
            return False
        else:
            if index == 0 or index == len(nums) - 2:
                return True
            elif nums[index - 1] <= nums[index + 1]:
                return True
            elif nums[index] <= nums[index + 2]:
                return True
            else:
                return False

• Version 2

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

        if count == 0 or index == 0 or index == len(nums) - 2 or nums[index - 1] <= nums[index + 1] or nums[index] <= nums[index + 2]:
            return True
        else:
            return False

Reference

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