来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-eaten-apples

题目描述

有一棵特殊的苹果树，一连 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
解释：你可以吃掉 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 才成立

解题思路

本题使用贪心算法进行模拟求解，每次找到最快腐烂的苹果吃掉，并且扔掉已经腐烂的苹果，便可以使得吃的苹果数目最多（虽然可能永远吃不到新鲜苹果）

如果每一天都进行一次查找，时间复杂度会非常高，所以采用优先队列的方式，永远将快腐烂的苹果放在堆顶。

想法1.0：

首先将每天产生的苹果数量的腐烂日期一个一个的存入优先队列，然后寻找队列中腐烂的苹果扔掉，最后取堆顶的苹果吃掉，直到队列为空的那天为止。

由于一天可能产生的苹果数量也非常多，所以时间复杂度依然很高，不能将苹果一个一个存入优先队列。

想法2.0：

利用一个类来记录腐烂时间和数量，将产生的苹果打包直接全部放入优先队列中，然后寻找优先队列中已经腐烂的苹果包或者苹果包中没有苹果的苹果包丢掉，取出腐烂日期最近的苹果包吃一个再放入。直到队列中没有苹果包为止。

代码展示

class Solution {

public:

    class Item

    {

    public:

        int miDay;

        int miCount;

        Item(int iDay, int iCount)

        {

            this->miDay = iDay;

            this->miCount = iCount;

        }

        bool operator<(const Item& other)  const

        {

            return this->miDay > other.miDay;

        }

    };

    int eatenApples(vector<int>& apples, vector<int>& days) {

        priority_queue<Item> pqiQueue;

        int iDay = 0, iRet = 0;

        while(iDay < apples.size() || !pqiQueue.empty())

        {

            if(iDay < apples.size())

            {

                pqiQueue.push(Item (iDay + days[iDay], apples[iDay]));

            }

            while(!pqiQueue.empty() && (pqiQueue.top().miDay <= iDay || pqiQueue.top().miCount < 1))

            {

                pqiQueue.pop();

            }

            if(!pqiQueue.empty())

            {

                Item zTemp = pqiQueue.top();

                pqiQueue.pop();

                zTemp.miCount--;

                if(zTemp.miCount > 0)

                {

                    pqiQueue.push(zTemp);

                }

                iRet++;

            }

            iDay++;

        }

        return iRet;

    }

};

巴特西

LeetCode-1705 吃苹果的最大数目

题目描述

解题思路

代码展示

运行结果

最新文章

热门文章