maximum-fruits-harvested-after-at-most-k-steps

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array <code>fruits</code> where <code>fruits[i] = [positioni, amounti]</code> depicts <code>amounti</code> fruits at the position <code>positioni</code>. <code>fruits</code> is already sorted by <code>positioni</code> in ascending order, and each <code>positioni</code> is unique.

You are also given an integer <code>startPos</code> and an integer <code>k</code>. Initially, you are at the position <code>startPos</code>. From any position, you can either walk to the left or right. It takes one step to move one unit on the x-axis, and you can walk at most <code>k</code> steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position.

Return the maximum total number of fruits you can harvest.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/1.png" style="width: 472px; height: 115px;" />
<pre>
Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation: 
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/2.png" style="width: 512px; height: 129px;" />
<pre>
Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
Output: 14
Explanation: 
You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
The optimal way is to:
- Harvest the 7 fruits at the starting position 5
- Move left to position 4 and harvest 1 fruit
- Move right to position 6 and harvest 2 fruits
- Move right to position 7 and harvest 4 fruits
You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/3.png" style="width: 476px; height: 100px;" />
<pre>
Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
Output: 0
Explanation:
You can move at most k = 2 steps and cannot reach any position with fruits.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= fruits.length &lt;= 105</code></li>
	<li><code>fruits[i].length == 2</code></li>
	<li><code>0 &lt;= startPos, positioni &lt;= 2 * 105</code></li>
	<li><code>positioni-1 &lt; positioni</code> for any <code>i &gt; 0</code>&nbsp;(0-indexed)</li>
	<li><code>1 &lt;= amounti &lt;= 104</code></li>
	<li><code>0 &lt;= k &lt;= 2 * 105</code></li>
</ul>

maxTotalFruits

Maximum Fruits Harvested After at Most K Steps

Maximum Performance of a Team

maximum-performance-of-a-team

最大的团队表现值

Array

Binary Search

Prefix Sum

Sliding Window

在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 <code>fruits</code> ，其中 <code>fruits[i] = [positioni, amounti]</code> 表示共有 <code>amounti</code> 个水果放置在 <code>positioni</code> 上。<code>fruits</code> 已经按 <code>positioni</code> 升序排列 ，每个 <code>positioni</code> 互不相同 。

另给你两个整数 <code>startPos</code> 和 <code>k</code> 。最初，你位于 <code>startPos</code> 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 <code>k</code> 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的 最大总数 。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/1.png" style="width: 472px; height: 115px;">
<pre>输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/2.png" style="width: 512px; height: 129px;">
<pre>输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出：14
解释：
可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果
</pre>

示例 3：
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/3.png" style="width: 476px; height: 100px;">
<pre>输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出：0
解释：
最多可以移动 k = 2 步，无法到达任一有水果的地方
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= fruits.length &lt;= 105</code></li>
	<li><code>fruits[i].length == 2</code></li>
	<li><code>0 &lt;= startPos, positioni &lt;= 2 * 105</code></li>
	<li>对于任意 <code>i &gt; 0</code> ，<code>positioni-1 &lt; positioni</code> 均成立（下标从 0 开始计数）</li>
	<li><code>1 &lt;= amounti &lt;= 104</code></li>
	<li><code>0 &lt;= k &lt;= 2 * 105</code></li>
</ul>