What is the main pattern used in Minimum Cost to Reach Every Position?

The problem follows an array-driven solution pattern where you track and propagate the minimum cost to reach each position efficiently.

Why is backward iteration important in this problem?

Iterating backward ensures that the running minimum cost is correctly applied to all earlier positions, avoiding redundant calculations.

Can I use nested loops to compute the minimum cost?

Using nested loops is unnecessary and less efficient; a single backward pass with a running minimum achieves optimal results.

How do lower-cost positions affect the strategy?

Reaching a lower-cost position early allows free movement to subsequent positions, minimizing the total swap cost.

What are the constraints on the input array cost?

The array length n satisfies 1 <= n <= 100, and each cost[i] is between 1 and 100.

#3502

Easy

auto_awesome数组·driven

LeetCode 题解工作台

到达每个位置的最小费用

给你一个长度为 n 的整数数组 cost 。当前你位于位置 n （队伍的末尾），队伍中共有 n + 1 人，编号从 0 到 n 。你希望在队伍中向前移动，但队伍中每个人都会收取一定的费用才能与你交换位置。与编号 i 的人交换位置的费用为 cost[i] 。你可以按照以下规则与他人交换位置： …

数组

题目描述

给你一个长度为 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

lightbulb

解题思路

方法一：脑筋急转弯

根据题目描述，每个位置 $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)$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	complexity is O(n) since each position is processed once, and space complexity is O(n) for storing the output array of minimum costs.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you maintaining the minimum cost encountered as you iterate through the array?
question_mark
Can you explain why swapping to a lower-cost position helps reduce future costs?
question_mark
How would your approach change if swaps could move backward as well?

warning

常见陷阱

外企场景

error
Forgetting to update the running minimum at each step, leading to overestimated costs.
error
Attempting nested loops for each position instead of using a single pass, causing unnecessary time complexity.
error
Not propagating lower costs forward, missing the free movement to later positions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow swapping with multiple people at once, changing the propagation logic of minimum costs.
arrow_right_alt
Modify costs dynamically during swaps, requiring recomputation of minimums on the fly.
arrow_right_alt
Compute minimum cost to reach only a specific subset of positions instead of all positions.

help

常见问题

外企场景

继续练习

#3501 操作后最大活跃区段数 II #3500 将数组分割为子数组的最小代价 #3505 使 K 个子数组内元素相等的最少操作数