题目

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

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


示例 1:

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

示例 2:

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


分析

  • 循环遍历判断当前循环的值 是否大于 下一个位置的值

    • 判断当前位置是否为数组的第一位置a[0]

      • 将现在位置的值等于下一个值,则使得,1号位,2号位 数值相等
    • 判断上一位的值是否大于下一位的值,例如:
      3,4,2
      当前遍历到4了,上一位3 大于 下一位2,要使这三个数成非递减,则将当前值赋值给下一位的值
      即 a[i+1] = a[i] ==> 3,4,4
    • 判断上一位的值是否小于下一位的值,例如:
      -1,4,2,3
      当前遍历到4了,上一位-1 小于 下一位2,要使这三个数成非递减,则将下一位的值赋值给当前值
      即 a[i] = a[i+1] ==> -1,2,2,3
      或者 将上一位的值赋值给当前位
      即 a[i] = a[i-1] ==> -1,-1,2,3
    • 最后break退出循环,因为只需要修改一次
  • 再用一次循环遍历

    • 遍历内的判断条件为,当前位的值是否大于下一位的值,成立,则直接返回false
    • 循环遍历完了都没有满足判断条件,则返回True

代码

class Solution:
    def checkPossibility(self, nums):
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                if i == 0:
                    nums[i] = nums[i+1]
                elif nums[i-1] > nums[i+1]:
                    nums[i+1] = nums[i]
                elif nums[i-1] < nums[i+1]:
                    nums[i] = nums[i+1]
                break
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                return False
        return True
Last modification:November 13th, 2019 at 05:10 pm