子寒的博客
0%

leetcode665 Non-decreasing Array 解题报告

发表于 更新于 分类于

英文原题

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).

分析

    题目需要判断所给列表是否可以只变动最多一个数字成为一个非递减序列。首先分析什么样的数组具备变为非递减的潜质，本身就符合当然不必说，除此之外我们可以把数组尽可能少的拆分成多个小的非递增序列，如（1，2，4，3，5，3，7）可拆分为（1，2，4和3，5和3，7）那么不难发现拆分出的小序列在两个以内才可能成为非递增。然后分析这个数字会在哪，题目中给了非递减序列的解释，那么我们就不难发现我们要找的这个点就是两个非递减序列的中间点，举个例子：     对于序列：（1，2，3，4，5，3，5，6）这个数字我们可能会想变第5个数字（5）或者第6个数字（3）然后发现5不可以但是如果3变成5的话就可以了。

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        trans_point = -1
        n = len(nums)
        
        for i in range(n-1):
            if nums[i] <= nums[i+1]:
                continue
            else:
                if trans_point >= 0:
                    return False
                else:
                    trans_point = i
                    
        if trans_point == -1 or trans_point == n-2 or trans_point == 0:
            return True
        if nums[trans_point] <= nums[trans_point+2] or nums[trans_point-1] <= nums[trans_point+1]:
            return True
        return False