查找要删除的最短子数组以使数组在 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
以上是 查找要删除的最短子数组以使数组在 Python 中排序的程序 的全部内容， 来源链接： utcz.com/z/349098.html
