0665._Non-decreasing_Array.md

665. Non-decreasing Array

难度: Easy

刷题内容

原题连接

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

内容描述

Given an array 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 array[i] <= array[i + 1] holds for every i (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: The n belongs to [1, 10,000].

解题方案

思路 1

从index=1的元素依次检查，只要不符合规则则让count+1，如果count>1则肯定不符合返回False 但是我们在发现nums[i]小于nums[i-1]的时候，我们就必须要对原数组作出改变了，来让它的后面index部分尽可能满足条件 下面就是两种情况：

• 2,4,2,6

如果是这种情况，当index=2时，不满足条件，但是i=0的元素是小于i=2处元素的，我们需要改变的是i-1处的元素，也就是将4改变成i=2处元素即2，最终变成2,2,2,6

• 3,4,2,6

这种情况如果我们将4变成2那么仍然是不满足条件的，此时我们需要将2变成4，即将i处元素变为i-1处元素

在每一次不符合条件的时候我们都检查一下count，如果count大于1的话我们就返回False，否则最终就返回True

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