求数组移除k个连续元素后最小振幅的O(N)复杂度JavaScript解法

删除k个连续元素等价于保留数组中长度为k的连续窗口之外的所有元素，我们只需要遍历所有可能的删除窗口，计算每个窗口对应剩余元素的振幅，取最小值即可。

核心预处理步骤 #

我们提前用O(N)时间预处理4个数组，避免每次计算剩余元素的最大/最小值时重复遍历：

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

计算最小振幅 #

遍历所有长度为k的删除窗口，分三种情况计算振幅：

1. 删除最左侧k个元素：剩余元素为下标k到末尾，振幅为 suffix_max[k] - suffix_min[k]
2. 删除最右侧k个元素：剩余元素为下标0到n-k-1，振幅为 prefix_max[n-k-1] - prefix_min[n-k-1]
3. 删除中间的连续k个元素：假设删除窗口左端点为i（范围1 ≤ i ≤ n-k-1），剩余元素为0到i-1的前缀 + i+k到末尾的后缀，振幅为 max(prefix_max[i-1], suffix_max[i+k]) - min(prefix_min[i-1], suffix_min[i+k])

遍历所有窗口取最小振幅即可，整体时间复杂度为O(N)，空间复杂度为O(N)。

function minAmplitudeAfterDeleteK(A, k) {
    const n = A.length;
    // 边界情况：删除所有元素，剩余元素振幅为0
    if (k >= n) return 0;
    
    // 预处理前缀最大最小值
    const prefixMax = new Array(n);
    const prefixMin = new Array(n);
    prefixMax[0] = A[0];
    prefixMin[0] = A[0];
    for (let i = 1; i < n; i++) {
        prefixMax[i] = Math.max(prefixMax[i-1], A[i]);
        prefixMin[i] = Math.min(prefixMin[i-1], A[i]);
    }
    
    // 预处理后缀最大最小值
    const suffixMax = new Array(n);
    const suffixMin = new Array(n);
    suffixMax[n-1] = A[n-1];
    suffixMin[n-1] = A[n-1];
    for (let i = n-2; i >= 0; i--) {
        suffixMax[i] = Math.max(suffixMax[i+1], A[i]);
        suffixMin[i] = Math.min(suffixMin[i+1], A[i]);
    }
    
    // 初始最小振幅取删最左或者删最右的最小值
    let minAmp = Math.min(suffixMax[k] - suffixMin[k], prefixMax[n - k - 1] - prefixMin[n - k - 1]);
    
    // 遍历中间删除窗口
    for (let i = 1; i <= n - k - 1; i++) {
        const currentMax = Math.max(prefixMax[i-1], suffixMax[i + k]);
        const currentMin = Math.min(prefixMin[i-1], suffixMin[i + k]);
        minAmp = Math.min(minAmp, currentMax - currentMin);
    }
    
    return minAmp;
}

// 测试示例
console.log(minAmplitudeAfterDeleteK([8,7,4,1], 2)); // 输出 1

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