美文网首页随笔
Leetcode 665. 非递减数列

Leetcode 665. 非递减数列

作者: zhipingChen | 来源:发表于2019-12-01 14:56 被阅读0次

    题目描述

    给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。

    我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。

    示例 1:

    输入: [4,2,3]
    输出: True
    解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

    示例 2:

    输入: [4,2,1]
    输出: False
    解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

    解法

    由题目可知,此处非递减数列的定义为:数列中每个元素值不小于其前面的元素值。

    由于只能更改一个元素值,不妨定义变量 flag 表示是否已经对数列中某个元素值进行了更改。遍历数列,若在位置 i 处有 nums[i]>nums[i+1],比较 i 位置前后的两个元素,若 nums[i+1]<nums[i-1],则更改 nums[i+1]=nums[i],否则更改 nums[i]=nums[i+1] 即可。

    因为遍历的下一个元素位置为 i+1,所以没有必要执行 nums[i]=nums[i+1] 的操作。

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

    相关文章

      网友评论

        本文标题:Leetcode 665. 非递减数列

        本文链接:https://www.haomeiwen.com/subject/hjvzwctx.html