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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告