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+ 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習