Python 中的非递减数组

假设我们有一个包含 n 个整数的数组，我们的任务是检查它是否可以通过修改最多一个元素变成非递减的。我们可以定义一个数组是非递减的，如果它满足以下规则：对于每个 i（1 <= i < n），array[i] <= array[i + 1]。所以如果数组是 [4,2,3]，那么答案将是真。如果我们将 4 更改为 1，我们可以简单地将其转换为非递减数组，那么数组将是 [1,2,3]

为了解决这个问题，我们将遵循以下步骤 -

• 如果 arr 包含 2 个或更少的元素，则返回 true

• ans := False

• 对于 i 的范围从 0 到 arr 中元素的数量 – 2

  • 如果 arr[i] > arr[i + 1]

    • 如果 ans 为非 0，则返回 false，否则 ans := True

    • 如果 i > 0

      • 如果 arr[i - 1] > arr[i + 1]，则 arr[i + 1] := arr[i]

• 返回 true

示例（Python）

让我们看看以下实现以更好地理解 -

 实时演示

class Solution(object):
   def checkPossibility(self, nums):
      if len(nums) <=2:
         return True
      ans = False
      for i in range(len(nums)-1):
         if nums[i] > nums[i+1]:
            if ans:
               return False
            else:
               ans = True
            if i>0:
               if nums[i-1] > nums[i+1]: nums[i+1] = nums[i]
      return True
ob1 = Solution()
print(ob1.checkPossibility([4,2,3,5]))

输入

[4,2,3,5]

输出

True

Arnab Chakraborty

更新于: 2020-04-27

1K+ 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习