2106. 摘水果

业精于勤，荒于嬉;行成于思，毁于随。

LeetCode 每日一题，参考2106. 摘水果，难度分2062。

题目

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

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

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

解题思路

• 前缀和：可以枚举两种情况,一种是向左走再回来,一种是向右走再回来,计算两种情况摘的水果的最大值即可,此时要计算区间和,可以使用前缀和简化计算。

前缀和

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        //用前缀和计算到达区间的水果收益
        int n = fruits.length, maxPos = fruits[n-1][0];
        int[] preSum = new int[Math.max(maxPos+1,startPos+k+1)+1];
        for(int i = 0,j = 0;i < preSum.length-1; i++) {
            if(j < n && i == fruits[j][0]) {
                preSum[i+1] = preSum[i] + fruits[j][1];
                j++;//比较下一个水果
            } else {
                preSum[i+1] = preSum[i];
            }
        }
        //枚举区间找最大  
        int ans = 0;
        //枚举左边走多少步
        for(int i = 0; i <= k; i++) {
            //计算右边到达最大位置
            int leftPos = startPos - i,leftSteps = k - i;
            int rightPos = Math.max(leftPos + leftSteps,startPos);
            ans = Math.max(ans,preSum[rightPos+1]-preSum[Math.max(leftPos,0)]);
        }
        //枚举右边走多少步
        for(int i = 0; i <= k; i++) {
            //计算左边到达最小位置
            int rightPos = startPos + i,leftSteps = k - i;
            int leftPos = Math.min(Math.max(0,rightPos - leftSteps),startPos);
            ans = Math.max(ans,preSum[rightPos+1]-preSum[leftPos]);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，一重循环遍历,n为前缀和长度。
• 空间复杂度：O(n)，即前缀和使用空间。