2023-05-04每日一题

一、题目编号

2106. 摘水果

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

四、解题代码

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int n = fruits.size();
        long long sum[400010];
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < n; ++i){
            sum[fruits[i][0]] = fruits[i][1]; 
        }
        for(int i = 1; i <= 200000; ++i){
            sum[i] += sum[i-1];
        }
        if(startPos == 0){
            return sum[min(200000, k)];
        }
        long long max0 = 0;
        for(int i = 0; i <= k; ++i){
            if(i == startPos){
                max0 = max(max0 ,sum[max(startPos, startPos - 2 * i + k)]);
            } else if(i < startPos){
                max0 = max(max0, sum[max(startPos, startPos - 2 * i + k )] - sum[startPos - i - 1]);
            }

            if(startPos + i <= 200000){
                if(max(k - 2 * i, 0) >= startPos){
                    max0 = max(sum[startPos + i], max0);
                } else{
                    max0 = max(max0, sum[startPos + i] - sum[startPos - max(k - 2 * i, 0) - 1]);     
                }
            }
        }
    return max0;
    }
};

五、解题思路

(1) 首先我们思考能走多少步，设步数为i。我们很容易可以根据题目来知晓，这个步数为0 ~ k。

(2) 那我们将问题转化成，我们该如何规划这i步，使得摘到的水果最多。我们根据贪心的原理可以很容易知晓，我们应该尽可能的利用上我们的步数。那么我们的问题就转化成一开始是往右走，还是一开始往左走。

(3) 这样我们可以根据往左走或者往右走的步数，规划出一个窗口。计算出该窗口中水果的数目，只要取水果数目最大的窗口即为最终的答案。

(4) 最后我们只需要用前缀和来求出遍历到的每一个窗口中水果的数目即可。