移除K个连续元素使数组剩余元素振幅最小的解决方案及前缀后缀最值方法解析

嘿，这个问题我刚好琢磨过，咱们把这个前缀后缀的思路拆解开，保证你能彻底搞懂~

首先得明确：移除K个连续元素后，剩余的元素必然是数组的一段前缀（可能为空）加上一段后缀（可能为空）。比如你的示例中，移除前4个元素，剩下的就是后缀[9,8]；如果移除中间的4个（索引1到4），剩下的就是前缀[3]加后缀[8]；如果移除后4个，剩下的就是前缀[3,5]。所以我们只需要枚举所有可能的“前缀长度+对应后缀”的组合，计算每种组合的振幅，再取最小值就行。

前缀数组和后缀数组的核心是提前预处理出所有可能的前缀、后缀的极值（最大值和最小值），这样我们不需要每次枚举组合时都重新遍历计算极值，能把时间复杂度降到O(n)。

具体来说，我们需要四个数组：

• prefix_min[i]：数组前i个元素（A[0]到A[i-1]）的最小值
• prefix_max[i]：数组前i个元素的最大值
• suffix_min[i]：从A[i]到数组末尾的最小值
• suffix_max[i]：从A[i]到数组末尾的最大值

举个你的例子A=[3,5,1,3,9,8]：

• prefix_min数组是：[inf, 3, 3, 1, 1, 1, 1]（prefix_min[0]设为无穷大，因为前0个元素没有值）
• prefix_max数组是：[-inf, 3, 5, 5, 5, 9, 9]
• suffix_min数组是：[1, 1, 1, 3, 8, 8, inf]（suffix_min[6]设为无穷大，因为从索引6开始没有元素）
• suffix_max数组是：[9, 9, 9, 9, 9, 8, -inf]

接下来，我们遍历所有可能的前缀长度i（i的范围是0到n-K，n是数组长度）：

• 当选择前缀长度为i时，我们需要移除从索引i到i+K-1的连续K个元素，剩下的后缀就是从索引i+K开始到末尾的部分。
• 此时剩余元素的最小值是min(prefix_min[i], suffix_min[i+K])，最大值是max(prefix_max[i], suffix_max[i+K])
• 计算这个组合的振幅（max - min），并记录所有组合中的最小值。

还是用你的示例，n=6，K=4，n-K=2，i可以取0、1、2：

• i=0：前缀为空，后缀从索引4开始，min是8，max是9，振幅1
• i=1：前缀是[3]，后缀是[8]，min是3，max是8，振幅5
• i=2：前缀是[3,5]，后缀为空，min是3，max是5，振幅2
  所以最小振幅就是1，和示例结果一致。

下面是完整的代码，你可以直接运行测试：

def minimal_amplitude(A, K):
    n = len(A)
    if K >= n:
        return 0  # 移除所有元素，振幅为0
    
    # 预处理前缀min和max
    prefix_min = [float('inf')] * (n + 1)
    prefix_max = [float('-inf')] * (n + 1)
    for i in range(1, n + 1):
        prefix_min[i] = min(prefix_min[i-1], A[i-1])
        prefix_max[i] = max(prefix_max[i-1], A[i-1])
    
    # 预处理后缀min和max
    suffix_min = [float('inf')] * (n + 1)
    suffix_max = [float('-inf')] * (n + 1)
    for i in range(n-1, -1, -1):
        suffix_min[i] = min(suffix_min[i+1], A[i])
        suffix_max[i] = max(suffix_max[i+1], A[i])
    
    min_amp = float('inf')
    # 枚举所有可能的前缀长度
    for i in range(n - K + 1):
        # 获取当前组合的极值
        if i == 0:
            current_min = suffix_min[i+K]
            current_max = suffix_max[i+K]
        elif i + K == n:
            current_min = prefix_min[i]
            current_max = prefix_max[i]
        else:
            current_min = min(prefix_min[i], suffix_min[i+K])
            current_max = max(prefix_max[i], suffix_max[i+K])
        
        min_amp = min(min_amp, current_max - current_min)
    
    return min_amp

# 测试示例
A = [3,5,1,3,9,8]
K = 4
print(minimal_amplitude(A, K))  # 输出1

如果数组规模很小（比如n<1000），也可以用暴力枚举法：

• 遍历所有可能的移除起始索引i（0<=i<=n-K）
• 移除A[i:i+K]后，计算剩余元素的min和max，得到振幅
• 取所有振幅的最小值

但这个方法的时间复杂度是O(n^2)，当n很大时会超时，所以前缀后缀的O(n)方法是更优的选择。

内容的提问来源于stack exchange，提问作者some_one_rand