Easy

题目描述

给你一个大小为 n 的整数数组 cost。你目前在一列 n + 1 个人（编号从 0 到 n）的末尾位置 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：我们可以与第 0 个人交换，成本为 5。
- i = 1：我们可以与第 1 个人交换，成本为 3。
- i = 2：我们可以与第 1 个人交换，成本为 3，然后免费与第 2 个人交换。
- i = 3：我们可以与第 3 个人交换，成本为 1。
- i = 4：我们可以与第 3 个人交换，成本为 1，然后免费与第 4 个人交换。
- i = 5：我们可以与第 3 个人交换，成本为 1，然后免费与第 5 个人交换。

示例 2：

输入：cost = [1,2,4,6,7]
输出：[1,1,1,1,1]
解释：
我们可以与第 0 个人交换，成本为 1，然后免费到达任何位置 i。

约束条件：

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

解题思路

解题思路

这道题的关键在于理解交换规则：我们只能向前（位置编号减小）移动，且一旦到达某个位置，就可以免费与后面的任何人交换。

核心观察

  1. 我们从位置 n 开始，想要到达位置 i（i < n）
  2. 与前面的人交换需要付费，与后面的人交换免费
  3. 一旦我们到达某个位置 j，就可以免费到达所有位置 k（k > j）

解法分析

贪心策略：对于每个位置 i，我们需要找到从当前位置到位置 i 的最小成本路径。

关键insight：到达位置 i 的最小成本等于从位置 i 到位置 n 的最小前缀成本。换句话说，我们需要找到区间 [i, n-1] 中的最小值。

算法步骤：

  1. 从右到左维护一个最小值
  2. 对于每个位置 i，answer[i] 就是从位置 i 到末尾的最小 cost 值
  3. 这是因为我们可以先移动到成本最低的位置，然后免费到达目标位置

这种方法的正确性在于：一旦我们到达了区间 [i, n-1] 中成本最低的位置，就可以免费移动到位置 i。

代码实现

class Solution {
public:
    vector<int> minCosts(vector<int>& cost) {
        int n = cost.size();
        vector<int> answer(n);
        
        // 从右到左维护最小值
        int minCost = cost[n-1];
        answer[n-1] = minCost;
        
        for (int i = n - 2; i >= 0; i--) {
            minCost = min(minCost, cost[i]);
            answer[i] = minCost;
        }
        
        return answer;
    }
};

class Solution:
    def minCosts(self, cost: List[int]) -> List[int]:
        n = len(cost)
        answer = [0] * n
        
        # 从右到左维护最小值
        min_cost = cost[n-1]
        answer[n-1] = min_cost
        
        for i in range(n-2, -1, -1):
            min_cost = min(min_cost, cost[i])
            answer[i] = min_cost
            
        return answer

public class Solution {
    public int[] MinCosts(int[] cost) {
        int n = cost.Length;
        int[] answer = new int[n];
        
        // 从右到左维护最小值
        int minCost = cost[n-1];
        answer[n-1] = minCost;
        
        for (int i = n - 2; i >= 0; i--) {
            minCost = Math.Min(minCost, cost[i]);
            answer[i] = minCost;
        }
        
        return answer;
    }
}

/**
 * @param {number[]} cost
 * @return {number[]}
 */
var minCosts = function(cost) {
    const n = cost.length;
    const answer = new Array(n);
    
    // 从右到左维护最小值
    let minCost = cost[n-1];
    answer[n-1] = minCost;
    
    for (let i = n - 2; i >= 0; i--) {
        minCost = Math.min(minCost, cost[i]);
        answer[i] = minCost;
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：只需要遍历数组一次
  • 空间复杂度：除了输出数组外，只使用了常数额外空间