Python程式：查詢最短子陣列以使陣列排序

假設我們有一個名為 arr 的陣列，我們需要移除 arr 的一個子陣列，使得 arr 中剩餘的元素按非遞減順序排列。我們需要找到要移除的最短子陣列的長度。

因此，如果輸入類似於 arr = [10,20,30,100,40,20,30,50]，則輸出將為 3，因為我們可以移除 [100, 40, 20]，其長度為 3 的最小子陣列，並且透過移除這些，所有元素都按非遞減順序排列 [10,20,30,30,50]。

為了解決這個問題，我們將遵循以下步驟

  • n := arr 的大小
  • arr := 在 arr 的左側插入 0，在右側插入無窮大
  • A，B := 兩個新的空列表
  • p := 1，q:= arr 的大小 -2
  • M := 0
  • 當 p <= q 時，執行以下操作
    • 如果 arr[p-1] <= arr[p]，則
      • 將 arr[p] 插入 A 的末尾
      • p := p + 1
    • 否則，當 arr[q] <= arr[q+1] 時，則
      • 將 arr[q] 插入 B 的末尾
      • 當 A 不為空且 A 的最後一個元素 > B 的最後一個元素時，執行以下操作
        • 從 A 中刪除最後一個元素
      • q := q - 1
    • 否則，
      • 退出迴圈
    • M := M 和 A 的大小 + B 的大小的最大值
  • 返回 n - M

讓我們看看下面的實現以獲得更好的理解

示例

def solve(arr):
   n = len(arr)
   arr = [0] + arr + [float("inf")]
   A,B=[],[]
   p,q=1,len(arr)-2
   M = 0
   while p <= q:
      if arr[p-1] <= arr[p]:
         A.append(arr[p])
         p += 1
      elif arr[q] <= arr[q+1]:
         B.append(arr[q])
         while A and A[-1] > B[-1]:
            A.pop()
         q -= 1
      else:
         break
      M = max(M, len(A)+len(B))
   return n - M
arr = [10,20,30,100,40,20,30,50]
print(solve(arr))

輸入

[10,20,30,100,40,20,30,50]

輸出

3

更新於: 2021年10月4日

226 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告