題目

題目鏈接🔗

有一棵特殊的蘋果樹，一連 $n$ 天，每天都可以長出若干個(gè)蘋果。在第 $i$ 天，樹上會(huì)長出 $apples[i]$ 個(gè)蘋果，這些蘋果將會(huì)在 $days[i]$ 天后（也就是說，第 $i+days[i]$ 天時(shí)）腐爛，變得無法食用。也可能有那么幾天，樹上不會(huì)長出新的蘋果，此時(shí)用 $apples[i]==0$ 且 $days[i]==0$ 表示。

你打算每天 最多 吃一個(gè)蘋果來保證營養(yǎng)均衡。注意，你可以在這 $n$ 天之后繼續(xù)吃蘋果。

給你兩個(gè)長度為 $n$ 的整數(shù)數(shù)組 $days$ 和 $apples$ ，返回你可以吃掉的蘋果的最大數(shù)目。

示例 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?10^4$
2. $0\le apples[i]\le 5?10^4$
3. $1\le days[i]\le 5?10^4$
4. 每天至少有一個(gè)蘋果，即 $apples.length==days.length$。

思路

這個(gè)問題可以通過貪心算法來解決。我們可以維護(hù)一個(gè)優(yōu)先隊(duì)列（最小堆），存儲(chǔ)未來幾天內(nèi)會(huì)壞掉的蘋果。每天，我們從隊(duì)列中移除已經(jīng)壞掉的蘋果，然后根據(jù)當(dāng)前的蘋果數(shù)量和剩余天數(shù)來決定每天可以吃多少蘋果。

代碼

class Solution {
public:int eatenApples(vector<int>& apples, vector<int>& days) {int d = 0, ans = 0;map<int, int> dict; // 存儲(chǔ)未來幾天內(nèi)會(huì)壞掉的蘋果for (auto [n, t] : views::zip(apples, days)) {// 移除已經(jīng)壞掉的蘋果dict.erase(dict.begin(), dict.upper_bound(d));// 添加今天的蘋果if (n)dict[d + t] += n;// 如果有蘋果可以吃if (dict.size()) {ans++;// 吃掉一個(gè)蘋果if (!--dict.begin()->second)dict.erase(dict.begin());}d++;}// 繼續(xù)吃剩下的蘋果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;}
};

復(fù)雜度分析

時(shí)間復(fù)雜度

$O(nlogn)$，其中 $n$ 是蘋果的天數(shù)。主要時(shí)間消耗在對(duì) map 的操作，每次插入和刪除操作的時(shí)間復(fù)雜度為 $O(logn)$。

空間復(fù)雜度

$O(n)$

結(jié)果

總結(jié)

本題是一個(gè)貪心算法的問題，關(guān)鍵在于理解如何維護(hù)一個(gè)存儲(chǔ)未來幾天內(nèi)會(huì)壞掉的蘋果的數(shù)據(jù)結(jié)構(gòu)，并據(jù)此計(jì)算每天可以吃多少蘋果。