3502. 到达每个位置的最小费用

题目描述

给你一个长度为 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 的人交换位置。

示例 2：

输入: cost = [1,2,4,6,7]

输出: [1,1,1,1,1]

解释:

可以花费 1 费用与编号 0 的人交换位置，然后可以免费到达队伍中的任何位置 i。

提示

1 <= n == cost.length <= 100
1 <= cost[i] <= 100

解法

方法一：脑筋急转弯

根据题目描述，每个位置 \(i\) 的最小费用，就是从 \(0\) 到 \(i\) 的最小费用。我们可以用一个变量 \(\textit{mi}\) 来记录从 \(0\) 到 \(i\) 的最小费用。

我们从 \(0\) 开始遍历每个位置 \(i\)，每次更新 \(\textit{mi}\) 为 \(\text{min}(\textit{mi}, \text{cost}[i])\)，然后将 \(\textit{mi}\) 赋值给答案数组的第 \(i\) 个位置。

最后返回答案数组即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(\textit{cost}\) 的长度。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def minCosts(self, cost: List[int]) -> List[int]:
        n = len(cost)
        ans = [0] * n
        mi = cost[0]
        for i, c in enumerate(cost):
            mi = min(mi, c)
            ans[i] = mi
        return ans

class Solution {
    public int[] minCosts(int[] cost) {
        int n = cost.length;
        int[] ans = new int[n];
        int mi = cost[0];
        for (int i = 0; i < n; ++i) {
            mi = Math.min(mi, cost[i]);
            ans[i] = mi;
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> minCosts(vector<int>& cost) {
        int n = cost.size();
        vector<int> ans(n);
        int mi = cost[0];
        for (int i = 0; i < n; ++i) {
            mi = min(mi, cost[i]);
            ans[i] = mi;
        }
        return ans;
    }
};

func minCosts(cost []int) []int {
    n := len(cost)
    ans := make([]int, n)
    mi := cost[0]
    for i, c := range cost {
        mi = min(mi, c)
        ans[i] = mi
    }
    return ans
}

function minCosts(cost: number[]): number[] {
    const n = cost.length;
    const ans: number[] = Array(n).fill(0);
    let mi = cost[0];
    for (let i = 0; i < n; ++i) {
        mi = Math.min(mi, cost[i]);
        ans[i] = mi;
    }
    return ans;
}

3502. 到达每个位置的最小费用

题目描述

解法

方法一：脑筋急转弯

评论