Package g2101_2200.s2106_maximum_fruits_harvested_after_at_most_k_steps

Class Solution

java.lang.Object

g2101_2200.s2106_maximum_fruits_harvested_after_at_most_k_steps.Solution

public class Solution
extends Object

2106 - Maximum Fruits Harvested After at Most K Steps.<p>Hard</p> <p>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] = [position_i, amount_i]</code> depicts <code>amount_i</code> fruits at the position <code>position_i</code>. <code>fruits</code> is already <strong>sorted</strong> by <code>position_i</code> in <strong>ascending order</strong> , and each <code>position_i</code> is <strong>unique</strong>.</p> <p>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 <strong>left or right</strong>. It takes <strong>one step</strong> to move <strong>one unit</strong> on the x-axis, and you can walk <strong>at most</strong> <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.</p> <p>Return <em>the <strong>maximum total number</strong> of fruits you can harvest</em>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/11/21/1.png" alt="" /></p> <p><strong>Input:</strong> fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4</p> <p><strong>Output:</strong> 9</p> <p><strong>Explanation:</strong> The optimal way is to:</p> <ul> <li> <p>Move right to position 6 and harvest 3 fruits</p> </li> <li> <p>Move right to position 8 and harvest 6 fruits</p> </li> </ul> <p>You moved 3 steps and harvested 3 + 6 = 9 fruits in total.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/11/21/2.png" alt="" /></p> <p><strong>Input:</strong> fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4</p> <p><strong>Output:</strong> 14</p> <p><strong>Explanation:</strong> You can move at most k = 4 steps, so you cannot reach position 0 nor 10. The optimal way is to:</p> <ul> <li> <p>Harvest the 7 fruits at the starting position 5</p> </li> <li> <p>Move left to position 4 and harvest 1 fruit</p> </li> <li> <p>Move right to position 6 and harvest 2 fruits</p> </li> <li> <p>Move right to position 7 and harvest 4 fruits</p> </li> </ul> <p>You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.</p> <p><strong>Example 3:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/11/21/3.png" alt="" /></p> <p><strong>Input:</strong> fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> You can move at most k = 2 steps and cannot reach any position with fruits.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= fruits.length <= 10⁵</code></li> <li><code>fruits[i].length == 2</code></li> <li><code>0 <= startPos, position_i <= 2 * 10⁵</code></li> <li><code>position_i-1 < position_i</code> for any <code>i > 0</code> ( <strong>0-indexed</strong> )</li> <li><code>1 <= amount_i <= 10⁴</code></li> <li><code>0 <= k <= 2 * 10⁵</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	maxTotalFruits(int[][] fruits, int startPos, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

maxTotalFruits

public int maxTotalFruits(int[][] fruits,
 int startPos,
 int k)