删除k个连续元素求最小相邻差总和的O(n²)算法如何优化？

原O(n²)暴力解法会在大输入下超时，通过数学推导可以将时间复杂度降到O(n)，完全适配1e5规模的输入要求：

核心推导 #

先定义原数组不删除任何元素的总cost为total，计算方式为所有相邻元素差的绝对值之和：
total = sum_{i=1 to n-1} |arr[i] - arr[i-1]|
当删除起始下标为s的连续k个元素（即删除s ~ s+k-1区间）时，总cost的变化仅和区间前后的元素相关：

• 减去原总cost中，区间内所有相邻差、区间左端点和前一个元素的差、区间右端点和后一个元素的差
• 仅当删除区间不是数组首尾段时，新增一个差：区间前一个元素和区间后一个元素的差
  提前预处理差分数组的前缀和，即可O(1)计算任意删除区间对应的总cost。

实现步骤 #

1. 边界处理：如果数组长度n <=k，删除后剩余元素≤1，直接返回0
2. 预处理前缀和数组prefix，其中prefix[i]表示前i个相邻差的总和，即prefix[0] = 0，prefix[i] = prefix[i-1] + |arr[i] - arr[i-1]|
3. 遍历所有合法的删除起始位置s（范围0 <= s <= n-k），按规则计算当前删除后的总cost，记录最小值

static long process(List<Integer> arr, int k) {
    int n = arr.size();
    if (n <= k) return 0;
    // 预处理前缀和
    long[] prefix = new long[n];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + Math.abs(arr.get(i) - arr.get(i-1));
    }
    long total = prefix[n-1];
    long minCost = Long.MAX_VALUE;
    int maxS = n - k;
    for (int s = 0; s <= maxS; s++) {
        long currentCost;
        if (s == 0) {
            // 删除开头k个元素
            currentCost = total - prefix[k];
        } else if (s + k == n) {
            // 删除结尾k个元素
            currentCost = prefix[s];
        } else {
            // 删除中间连续段
            long subtract = prefix[s + k] - prefix[s-1];
            long add = Math.abs(arr.get(s + k) - arr.get(s-1));
            currentCost = total - subtract + add;
        }
        minCost = Math.min(minCost, currentCost);
    }
    return minCost;
}

• 时间复杂度：O(n)，仅需要两次线性遍历，可轻松处理1e5规模的输入
• 空间复杂度：O(n)，存储前缀和数组，空间消耗可忽略，也可根据需求优化到O(1)
  内容的提问来源于stack exchange，提问作者Learner