在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
- M := 0
- while p <= q,执行
- 如果 arr[p-1] <= arr[p],则
- 将 arr[p] 插入到 A 的末尾
- p := p + 1
- 否则当 arr[q] <= arr[q+1],则
- 将 arr[q] 插入到 B 的末尾
- while A 不为空 and A 的最后一个元素 > B 的最后一个元素,执行
- 从 A 中删除最后一个元素
- q := q – 1
- 否则,
- 退出循环
- M := A 的大小与 B 的大小之和的最大值
- 如果 arr[p-1] <= arr[p],则
- 返回 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