LeetCode - 非递减数列

Title:
    给定一个长度为n的整数数组,你的任务是判断在最多改变1个元素的情况下,该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的：对于数组中所有的i(1<=i<n),满足array[i]<=array[i+1]。

Input:
    [4,2,3]
    
Output:
    True
    
From:  LeetCode

分析

保证一个列表非递减，即后面一定大于等于前一个数，情况太多，我们反向排除不可能的选项：

• 1. 出现大于一次后面的数小于前面的数
• 2. 当上述情况仅存在一次时候，也会产生双折点情况，将数字按照高低排列(线性)，此时如果折点(最低点)的后项大于前项，或者折点(最高点)的前项小于后项，此时是可以跳过他们(折点)产生正确的非递减数列的，所以我们反向排除掉这种可能，使双折点情况高低错折，不能产生正解

代码

class Solution(object):

    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        Flag = 0
        for i in range(len(nums) - 1):
            if nums[i + 1] - nums[i] < 0:
                Flag += 1
                index = i
                if Flag > 1:
                    return False
        return False if (Flag == 1 and ((index >= 1 and nums[index-1] > nums[index+1]) and
                                    (index < len(nums)-2 and nums[index] > nums[index+2]))) else True