到达每个位置最小费用

题目

给你一个长度为 n 的整数数组 cost 。当前你位于位置 n（队伍的末尾），队伍中共有 n + 1 人，编号从 0 到 n 。

你希望在队伍中向前移动，但队伍中每个人都会收取一定的费用才能与你 交换位置。与编号 i 的人交换位置的费用为 cost[i] 。

你可以按照以下规则与他人交换位置：

如果对方在你前面，你 必须 支付 cost[i] 费用与他们交换位置。
如果对方在你后面，他们可以免费与你交换位置。
返回一个大小为 n 的数组 answer，其中 answer[i] 表示到达队伍中每个位置 i 所需的 最小 总费用。

 

示例 1：

输入: 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 的人交换位置。

解题思路

当你要到达i位置的时候，如果i位置前面的位置（0，i）中的cost，小于cost[i]，那么就可以选择跳转到min(cost[前面的位置])，然后免费向后交换。所以，这道题的关键是设计一个min_cost作为中间值，min_cost既存储上一次位置交换的最小值，也充当这次位置交换比较的值。

答题

class Solution(object):
    def minCosts(self, cost):
        n = len(cost)
        answer = [0]*n
        min_cost = float('inf') #初始化一个无穷大的数，作为“当前最小值”的初始比较基准。
        
        for i in range(n):
           min_cost = min(min_cost,cost[i])
           answer[i]= min_cost
        return answer