从阵列中删除n个连续元素，使剩余元素的振幅最小

Question

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

我在这里看到了一篇类似的帖子：Program to find minimal amplitude after removing consecutive elements from array，有人评论说使用前缀和后缀minimum和maximum，但我不知道这意味着什么，以及这会有什么帮助。如果有人能澄清/提供其他建议，那就太好了

Answer 1

具有前缀/后缀最小值/最大值的O（n）解：

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 = (∞,-∞)的配对对应于移除[3,5]后的左子阵列[3,5]和右子阵列[]。其中左侧和右侧的最小值为min(3,∞)=3，最大值为max(5,-∞)=5，振幅为5-3=2

针对naive暴力参考解决方案的十项随机测试：

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)