用 Python 编写程序，查找要删除的最短子数组，以使数组排序

pythonserver side programmingprogramming更新于 2025/11/26 9:16:17

假设我们有一个名为 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
M := 0
当 p <= q 时，执行
- 如果 arr[p-1] <= arr[p]，则
  - 在 A 末尾插入 arr[p]
  - p := p + 1
- 否则当 arr[q] <= arr[q+1] 时，则
  - 在 B 末尾插入 arr[q]
  - 当 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))