minimum-cost-to-reach-every-position

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code data-end="119" data-start="113">cost</code> of size <code data-end="131" data-start="128">n</code>. You are currently at position <code data-end="166" data-start="163">n</code> (at the end of the line) in a line of <code data-end="187" data-start="180">n + 1</code> people (numbered from 0 to <code data-end="218" data-start="215">n</code>).

You wish to move forward in the line, but each person in front of you charges a specific amount to swap places. The cost to swap with person <code data-end="375" data-start="372">i</code> is given by <code data-end="397" data-start="388">cost[i]</code>.

You are allowed to swap places with people as follows:

<ul data-end="632" data-start="488">
	<li data-end="572" data-start="488">If they are in front of you, you must pay them <code data-end="546" data-start="537">cost[i]</code> to swap with them.</li>
	<li data-end="632" data-start="573">If they are behind you, they can swap with you for free.</li>
</ul>

Return an array <code>answer</code> of size <code>n</code>, where <code>answer[i]</code> is the minimum total cost to reach each position <code>i</code> in the line.

&nbsp;
Example 1:

<div class="example-block">
Input: cost = [5,3,4,1,3,2]

Output: [5,3,3,1,1,1]

Explanation:

We can get to each position in the following way:

<ul>
	<li><code>i = 0</code>. We can swap with person 0 for a cost of 5.</li>
	<li><code>i = 1</code>. We can swap with person 1 for a cost of 3.</li>
	<li><code>i = 2</code>. We can swap with person 1 for a cost of 3, then swap with person 2 for free.</li>
	<li><code>i = 3</code>. We can swap with person 3 for a cost of 1.</li>
	<li><code>i = 4</code>. We can swap with person 3 for a cost of 1, then swap with person 4 for free.</li>
	<li><code>i = 5</code>. We can swap with person 3 for a cost of 1, then swap with person 5 for free.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: cost = [1,2,4,6,7]

Output: [1,1,1,1,1]

Explanation:

We can swap with person 0 for a cost of 1, then we will be able to reach any position <code>i</code> for free.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == cost.length &lt;= 100</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 100</code></li>
</ul>

第 443 场周赛

weekly-contest-443

minCosts

中级工程师

Minimum Cost to Reach Every Position

Array

给你一个长度为 <code>n</code> 的整数数组 <code data-end="119" data-start="113">cost</code> 。当前你位于位置 <code data-end="166" data-start="163">n</code>（队伍的末尾），队伍中共有 <code data-end="187" data-start="180">n + 1</code> 人，编号从 0 到 <code>n</code> 。

你希望在队伍中向前移动，但队伍中每个人都会收取一定的费用才能与你 交换位置。与编号 <code data-end="375" data-start="372">i</code> 的人交换位置的费用为 <code data-end="397" data-start="388">cost[i]</code> 。

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

<ul data-end="632" data-start="488">
	<li data-end="572" data-start="488">如果对方在你前面，你 必须 支付 <code data-end="546" data-start="537">cost[i]</code> 费用与他们交换位置。</li>
	<li data-end="632" data-start="573">如果对方在你后面，他们可以免费与你交换位置。</li>
</ul>

返回一个大小为 <code>n</code> 的数组 <code>answer</code>，其中 <code>answer[i]</code> 表示到达队伍中每个位置 <code>i</code> 所需的 最小 总费用。

&nbsp;

示例 1：

<div class="example-block">
输入: cost = [5,3,4,1,3,2]

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

解释:

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

<ul>
	<li><code>i = 0</code>。可以花费 5 费用与编号 0 的人交换位置。</li>
	<li><code>i = 1</code>。可以花费 3 费用与编号 1 的人交换位置。</li>
	<li><code>i = 2</code>。可以花费 3 费用与编号 1 的人交换位置，然后免费与编号 2 的人交换位置。</li>
	<li><code>i = 3</code>。可以花费 1 费用与编号 3 的人交换位置。</li>
	<li><code>i = 4</code>。可以花费 1 费用与编号 3 的人交换位置，然后免费与编号 4 的人交换位置。</li>
	<li><code>i = 5</code>。可以花费 1 费用与编号 3 的人交换位置，然后免费与编号 5 的人交换位置。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入: cost = [1,2,4,6,7]

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

解释:

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

&nbsp;

提示

<ul>
	<li><code>1 &lt;= n == cost.length &lt;= 100</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 100</code></li>
</ul>