求通过前缀操作使数组元素相等的最小成本的高效算法

核心思路 #

我们需要通过前缀加值操作让数组所有元素相等，每次操作成本为加值的绝对值。关键是将问题转化为差分序列分析，从而找到最优解：

定义数组的差分序列：对于原数组 arr，差分 d[i] = arr[i] - arr[i-1]（i >= 1），d[0] = arr[0]。
每次选择前缀 k 加 x 的操作，等价于：

• d[0] += x
• 若 k < n（n 为数组长度），则 d[k] -= x

我们的目标是让所有元素相等，即最终差分序列中 d[1..n-1] 全部为0（此时所有元素等于 d[0]）。要消除每个 d[i]（i >=1），最小成本就是其绝对值——因为任何操作对 d[i] 的影响只能通过选择前缀 i 实现，单次操作 x = d[i] 就能将 d[i] 置为0，成本为 |d[i]|，且这是最优的（多次操作的成本总和不会小于单次操作的绝对值）。

高效算法步骤 #

1. 若数组长度 ≤ 1，直接返回0（无需操作）。
2. 初始化总成本 total = 0。
3. 遍历数组从第2个元素（索引1）到末尾：
   • 计算当前元素与前一个元素的差值 diff = arr[i] - arr[i-1]
   • 将 abs(diff) 累加到 total 中。
4. 返回 total。

时间与空间复杂度 #

• 时间复杂度：O(n)，仅需一次遍历。
• 空间复杂度：O(1)，无需额外存储空间。

示例验证 #

输入：arr = [1, 2, 1, 5]

• 索引1：diff = 2-1 = 1 → total += 1（total=1）
• 索引2：diff =1-2 = -1 → total +=1（total=2）
• 索引3：diff=5-1=4 → total +=4（total=6）
  输出：6，与示例一致。

代码实现（Python） #

def min_cost(arr):
    if len(arr) <= 1:
        return 0
    total = 0
    for i in range(1, len(arr)):
        total += abs(arr[i] - arr[i-1])
    return total

# 示例测试
print(min_cost([1,2,1,5])) # 输出6

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