从数组中删除 n 个连续元素，使剩余元素的幅度最小

Question

给定数组 A，我需要删除 K 个连续元素，以便剩余元素的振幅（最大和最小元素之间的差异）最小。例如 A=[3,5,1,3,9,8], K=4, 答案应该是 1。我可以删除 [3,5,1,3] 得到 1.

我在这里看到了类似的 post：Program to find minimal amplitude after removing consecutive elements from array，有人评论说使用前缀和后缀的最小值和最大值，但我不知道这意味着什么，也不知道这会有什么帮助。如果有人可以 clarify/provide 其他建议，那就太好了。

Answer 1

O(n) 解 prefix/suffix minima/maxima:

def solution(A, K):
    pre = zip(acc(A, min, initial=inf),
              acc(A, max, initial=-inf))
    suf = list(zip(list(acc(A[::-1], min, initial=inf))[::-1],
                    list(acc(A[::-1], max, initial=-inf))[::-1]))
    return min(max(left[1], right[1]) - min(left[0], right[0])
               for left, right in zip(pre, suf[K:]))

对于您的例子 A = [3,5,1,3,9,8] 我们有前缀 minima/maxima 和后缀 minima/maxima:

pre: (∞,-∞) (3,3) (3,5) (1,5) (1,5) (1,9) (1,9)
suf:  (1,9) (1,9) (1,9) (3,9) (8,9) (8,8) (∞,-∞)

对齐 K = 4 之后，您有：

pre:                         (∞,-∞) (3,3) (3,5) (1,5) (1,5) (1,9) (1,9)
suf:  (1,9) (1,9) (1,9) (3,9) (8,9) (8,8) (∞,-∞)

例如left = (3,5)和right = (∞,-∞)的配对在去掉[1,3,9,8]后对应左子数组[3,5]和右子数组[]。其中左右边最小值min(3,∞)=3，最大值max(5,-∞)=5，幅度为5-3=2.

针对原始暴力参考解决方案的十个随机测试：

917 917 True
908 908 True
898 898 True
925 925 True
939 939 True
954 954 True
905 905 True
899 899 True
927 927 True
934 934 True

完整代码（Try it online!）：

from itertools import accumulate as acc
from math import inf
from random import choices

def solution(A, K):
    pre = zip(acc(A, min, initial=inf),
              acc(A, max, initial=-inf))
    suf = list(zip(list(acc(A[::-1], min, initial=inf))[::-1],
                    list(acc(A[::-1], max, initial=-inf))[::-1]))
    return min(max(left[1], right[1]) - min(left[0], right[0])
               for left, right in zip(pre, suf[K:]))

print(solution([3, 5, 1, 3, 9, 8], 4))

def naive(A, K):
    result = inf
    for i in range(len(A) + 1 - K):
        copy = A.copy()
        del copy[i : i+K]
        result = min(result, max(copy) - min(copy))
    return result

print(naive([3, 5, 1, 3, 9, 8], 4))

for _ in range(10):
    A = choices(range(1000), k=100)
    K = 50
    expect = naive(A, K)
    result = solution(A, K)
    print(expect, result, result == expect)

从数组中删除 n 个连续元素，使剩余元素的幅度最小

remove n consecutive elements from array, so that amplitude of remaining elements is minimal

python

arrays

dynamic-programming

amplitude