Leetcode_5638. 吃苹果的最大数目

【原题链接】

5638. 吃苹果的最大数目

【题目描述】

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

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

给你两个长度为 n 的整数数组 daysapples ,返回你可以吃掉的苹果的最大数目*。*

示例 1:

输入:apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出:7
解释:你可以吃掉 7 个苹果:
- 第一天,你吃掉第一天长出来的苹果。
- 第二天,你吃掉一个第二天长出来的苹果。
- 第三天,你吃掉一个第二天长出来的苹果。过了这一天,第三天长出来的苹果就已经腐烂了。
- 第四天到第七天,你吃的都是第四天长出来的苹果。

示例 2:

输入:apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出:5
解释:你可以吃掉 5 个苹果:
- 第一天到第三天,你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天,你吃的都是第六天长出来的苹果。

提示:

  • apples.length == n
  • days.length == n
  • 1 <= n <= 2 * 104
  • 0 <= apples[i], days[i] <= 2 * 104
  • 只有在 apples[i] = 0 时,days[i] = 0 才成立

【代码】

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        typedef pair<int, int> PII;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        int res = 0, n = days.size();
        for(int i = 0; i < 40000; i++){
            if(i < n)
                heap.push({i + days[i], apples[i]});
            while(heap.size() && heap.top().first <= i) heap.pop();
            if(heap.size()){
                res++;
                PII x = heap.top();
                heap.pop();
                if(--x.second)
                    heap.push(x);
            }
        }
        return res;
    }
};

执行用时: 928 ms

内存消耗: 46.1 MB

【时间复杂度】

O(nlogn)

【注意点】

  1. 其他解法:可以用别的数据结构找时间最小的苹果,比如multiset等
  2. 贪心,吃日期最近的(最快要不能吃的)那个苹果

评论