【Leetcode】1705. 吃苹果的最大数目

题目

题目链接🔗

有一棵特殊的苹果树，一连 $n$ 天，每天都可以长出若干个苹果。在第 $i$ 天，树上会长出 $apples[i]$ 个苹果，这些苹果将会在 $days[i]$ 天后（也就是说，第 $i+days[i]$ 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 $apples[i]==0$ 且 $days[i]==0$ 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 $n$ 天之后继续吃苹果。

给你两个长度为 $n$ 的整数数组 $days$ 和 $apples$ ，返回你可以吃掉的苹果的最大数目。

示例 1：

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]

输出：7

示例 2：

输入：apples = [3,0,0,5,0], days = [3,0,0,4,0]

输出：5

提示：

1. $1\le apples.length\le 5\ast 10^4$
2. $0\le apples[i]\le 5\ast 10^4$
3. $1\le days[i]\le 5\ast 10^4$
4. 每天至少有一个苹果，即 $apples.length==days.length$。

思路

这个问题可以通过贪心算法来解决。我们可以维护一个优先队列（最小堆），存储未来几天内会坏掉的苹果。每天，我们从队列中移除已经坏掉的苹果，然后根据当前的苹果数量和剩余天数来决定每天可以吃多少苹果。

代码

class Solution {
public:int eatenApples(vector<int>& apples, vector<int>& days) {int d = 0, ans = 0;map<int, int> dict; // 存储未来几天内会坏掉的苹果for (auto [n, t] : views::zip(apples, days)) {// 移除已经坏掉的苹果dict.erase(dict.begin(), dict.upper_bound(d));// 添加今天的苹果if (n)dict[d + t] += n;// 如果有苹果可以吃if (dict.size()) {ans++;// 吃掉一个苹果if (!--dict.begin()->second)dict.erase(dict.begin());}d++;}// 继续吃剩下的苹果while (dict.size()) {dict.erase(dict.begin(), dict.upper_bound(d));if (dict.empty())return ans;auto [t, n] = *dict.begin();dict.erase(dict.begin());int tmp = min(t - d, n);d += tmp;ans += tmp;}return ans;}
};

复杂度分析

时间复杂度

$O(nlogn)$，其中 $n$ 是苹果的天数。主要时间消耗在对 map 的操作，每次插入和删除操作的时间复杂度为 $O(logn)$。

空间复杂度

$O(n)$

结果

总结

本题是一个贪心算法的问题，关键在于理解如何维护一个存储未来几天内会坏掉的苹果的数据结构，并据此计算每天可以吃多少苹果。