查找要删除的最短子数组以使数组在 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，在 arr 右侧插入无穷大

• A,B := 两个新的空列表

• p := 1, q:= arr 的大小 -2

• 米：= 0

• 而 p <= q，做

• 从循环中出来

• 在 B 的末尾插入 arr[q]

• 当 A 不为空且 A 的最后一个元素 > B 的最后一个元素时，做

• q := q - 1

• 从 A 中删除最后一个元素

• 在 A 的末尾插入 arr[p]

• p := p + 1

• 如果 arr[p-1] <= arr[p]，则

• 否则当 arr[q] <= arr[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