2025-09-26：到达每个位置的最小费用。用go语言，给出一个长度为 n 的整数数组 cost。队伍中共有 n+1 个人，编号从 0 到 n，你一开始站在编号为 n 的队尾。目标是到达队伍中任意位置 i（0 ≤ i < n）。

交换规则如下：

o 与编号为 i 的人互换位置时，如果那个人当前在你之前（也就是比你靠前），你需要支付 cost[i] 作为费用；

o 如果那个人在你后面，与其互换是免费的。

请返回一个长度为 n 的数组 answer，其中 answer[i] 表示从初始位置（编号 n）移动到位置 i 所需的最小总费用。

1 <= n == cost.length <= 100。

1 <= cost[i] <= 100。

输入: cost = [5,3,4,1,3,2]。

输出: [5,3,3,1,1,1]。

解释:

我们可以通过以下方式到达每个位置：

i = 0。可以花费 5 费用与编号 0 的人交换位置。

i = 1。可以花费 3 费用与编号 1 的人交换位置。

i = 2。可以花费 3 费用与编号 1 的人交换位置，然后免费与编号 2 的人交换位置。

i = 3。可以花费 1 费用与编号 3 的人交换位置。

i = 4。可以花费 1 费用与编号 3 的人交换位置，然后免费与编号 4 的人交换位置。

i = 5。可以花费 1 费用与编号 3 的人交换位置，然后免费与编号 5 的人交换位置。

题目来自力扣3502。

问题理解与关键洞察

1. 问题场景：队伍中有 n+1 个人，编号从 0 到 n。您初始位于队尾编号 n，需要移动到任意位置 i（0 ≤ i < n）。交换规则如下：

o 如果与编号 i 的人交换时，该人在您当前位置之前（即索引更小），需支付费用 cost[i]。

o 如果该人在您之后（索引更大），交换免费。

2. 关键观察：由于向后交换（向索引更大的方向）免费，而目标位置i总在初始位置n之前（索引更小），最优策略是先支付费用向前交换（向索引更小的方向）到某个中间位置j（其中j ≤ i），然后免费向后交换到i。因此，移动到位置i的最小费用实际等于cost数组中从索引0到i的最小值（即前缀最小值）。这是因为一旦支付费用到达一个低成本位置j，就可以免费向右（向后）移动覆盖所有j之后的位置（包括i）。

算法过程描述

1. 初始化：算法直接使用输入的 cost 数组作为基础数组进行处理。该数组的长度为 n，其中 cost[i] 表示直接与位置 i 交换所需的费用。

2. 前缀最小值计算：算法从左到右遍历 cost 数组（从索引 1 开始到索引 n-1），逐步更新每个位置的值：

o 对于每个索引 i，将 cost[i] 更新为 cost[i] 和 cost[i-1] 中的较小值。这确保 cost[i] 始终存储从索引 0 到 i 的最小费用值。

3. 结果生成：遍历完成后，cost 数组中的每个元素 cost[i] 即为移动到位置 i 的最小总费用。数组直接被修改为结果数组 answer，无需额外构造。

示例验证

以输入 cost = [5, 3, 4, 1, 3, 2] 为例：

o 初始数组：[5, 3, 4, 1, 3, 2]。

o 遍历索引 1：cost[1] = min(3, 5) = 3 → 数组变为 [5, 3, 4, 1, 3, 2]。

o 遍历索引 2：cost[2] = min(4, 3) = 3 → 数组变为 [5, 3, 3, 1, 3, 2]。

o 遍历索引 3：cost[3] = min(1, 3) = 1 → 数组变为 [5, 3, 3, 1, 3, 2]。

o 遍历索引 4：cost[4] = min(3, 1) = 1 → 数组变为 [5, 3, 3, 1, 1, 2]。

o 遍历索引 5：cost[5] = min(2, 1) = 1 → 最终结果 [5, 3, 3, 1, 1, 1]，与题目输出一致。

复杂度分析

o 总的时间复杂度：算法需要一次遍历数组，每个元素进行常数次操作（比较和赋值），因此时间复杂度为 O(n)，其中 n 是 cost 数组的长度。

o 总的额外空间复杂度：算法原地修改输入数组，仅使用少量临时变量（如循环计数器），不依赖额外数据结构。因此，额外空间复杂度为 O(1)（常数空间）。

此方法高效利用了动态规划的思想，通过前缀最小值优化将问题简化为线性处理，适用于题目约束 n ≤ 100 的场景。

Go完整代码如下：

package main

import (
    "fmt"
)

func minCosts(cost []int) []int {
    for i := 1; i < len(cost); i++ {
        cost[i] = min(cost[i], cost[i-1])
    }
    return cost
}

func main() {
    cost := []int{5, 3, 4, 1, 3, 2}
    result := minCosts(cost)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_costs(cost):
    for i in range(1, len(cost)):
        cost[i] = min(cost[i], cost[i - 1])
    return cost

def main():
    cost = [5, 3, 4, 1, 3, 2]
    result = min_costs(cost)
    print(result) 

if __name__ == "__main__":
    main()

·

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。

·