By Long Luo
Leetcode 1705. 吃苹果的最大数目 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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 解释:你可以吃掉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 * 10^4 0 <= apples[i], days[i] <= 2 * 10^4 只有在 apples[i] = 0 时,days[i] = 0 才成立
下面记录下我做这道题的思考过程:
暴力
很明显,每过一天,可能就有苹果过期,那么最好 的方法是每天挑选最临近过期 的苹果吃,这样才能吃到最多的苹果,于是新建一个二维数组,分别存储苹果个数和过期时间。
之后遍历这个数组,使用一个指针指向数组下标,一个t i m e time t i m e 变量表示时间,时间每日递增,当苹果数> 0 > 0 > 0 和未过期时苹果数− 1 -1 − 1 ,如果不满足,数组下标i d x + + idx++ i d x + + ,代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public int eatenApples (int [] apples, int [] days) { int len = apples.length; int ans = 0 ; int [][] sorted = new int [len][2 ]; for (int i = 0 ; i < len; i++) { sorted[i][0 ] = apples[i]; sorted[i][1 ] = i + days[i]; } Arrays.sort(sorted, (o1, o2) -> o1[1 ] - o2[1 ]); int time = 0 ; int idx = 0 ; while (idx < len) { while (idx < len && (sorted[idx][0 ] <= 0 || sorted[idx][1 ] <= time)) { idx++; } if (idx < len && sorted[idx][1 ] > time) { sorted[idx][0 ]--; ans++; } time++; } return ans; }
但是,这个方法只通过了50个test cases,遇到下列用例就不适用了:
1 2 [2,1,1,4,5] [10,10,6,4,2]
那么问题出在什么地方呢?
因为排序结果会导致我们先吃了还没有长出来的果实,所以此方法不可行,需要修改。
贪心 + 优先队列(堆)
思路与算法:
很明显,我们需要一种数据结构来记录过期时间最早的苹果 ,而且因为时间变化 ,所以需要可以删减元素,那么方法一的数组就不太可行,那么容易想到使用优先队列 来存储苹果的过期时间,优先队列中最小的元素(即最早的腐烂日期)会最先被取出。
计算吃苹果的最大数目分成2 2 2 个阶段:
第一阶段是第0 0 0 天到第n − 1 n-1 n − 1 天;
第二阶段是第n n n 天及以后。
首先,如果t i m e < n time<n t i m e < n 或者堆不为空,如果当天有苹果生成( a p p l e [ t i m e ] > 0 ) (apple[time]>0) ( a p p l e [ t i m e ] > 0 ) ,先将苹果以二元组( a p p l e s [ t i m e ] , t i m e + d a y s [ t i m e ] ) (apples[time], time + days[time]) ( a p p l e s [ t i m e ] , t i m e + d a y s [ t i m e ] ) 形式加入小根堆中,继续模拟;
然后尝试从堆中取出 最后食用日期最早可食用 的苹果c u r cur c u r ,如果堆顶元素已过期,则抛弃;
如果吃掉c u r cur c u r 一个苹果后,仍有剩余,并且最后过期时间大于当前时间(尚未过期),将c u r cur c u r 重新入堆;
循环上述逻辑,直到所有苹果出堆。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public int eatenApples (int [] apples, int [] days) { if (apples == null || apples.length == 0 || days == null || days.length == 0 ) { return 0 ; } PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int []>() { @Override public int compare (int [] o1, int [] o2) { return o1[1 ] - o2[1 ]; } }); int len = apples.length; int ans = 0 ; int time = 0 ; while (time < len || !pq.isEmpty()) { if (time < len && apples[time] > 0 ) { pq.offer(new int []{apples[time], days[time] + time}); } while (!pq.isEmpty() && pq.peek()[1 ] <= time) { pq.poll(); } if (!pq.isEmpty()) { int [] curr = pq.poll(); curr[0 ]--; ans++; if (curr[0 ] > 0 && curr[1 ] > time) { pq.offer(curr); } } time++; } return ans; }
复杂度分析
时间复杂度:O ( n l o g n ) O(nlogn) O ( n l o g n ) ,其中n n n 是数组apples \textit{apples} apples 和days \textit{days} days 的长度。优先队列中最多有n n n 个元素,每个元素加入优先队列和从优先队列中取出各一次,每次操作的时间复杂度是O ( l o g n ) O(logn) O ( l o g n ) ,因此总时间复杂度是O ( n log n ) O(n \log n) O ( n log n ) 。
空间复杂度:O ( n ) O(n) O ( n ) ,空间复杂度主要取决于优先队列,优先队列中的元素个数不会超过n n n 。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗