There is a special kind of apple tree that grows apples every day for n days. On the ith day, the tree grows apples[i] apples that will rot after days[i] days, that is on day i + days[i] the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any apples, which are denoted by apples[i] == 0 and days[i] == 0.

You decided to eat at most one apple a day (to keep the doctors away). Note that you can keep eating after the first n days.

Given two integer arrays days and apples of length n, return the maximum number of apples you can eat.

Example 1:

Input: apples = [1,2,3,5,2], days = [3,2,1,4,2] Output: 7 Explanation: You can eat 7 apples: - On the first day, you eat an apple that grew on the first day. - On the second day, you eat an apple that grew on the second day. - On the third day, you eat an apple that grew on the second day. After this day, the apples that grew on the third day rot. - On the fourth to the seventh days, you eat apples that grew on the fourth day. 

Example 2:

Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2] Output: 5 Explanation: You can eat 5 apples: - On the first to the third day you eat apples that grew on the first day. - Do nothing on the fouth and fifth days. - On the sixth and seventh days you eat apples that grew on the sixth day. 

Constraints:

• apples.length == n
• days.length == n
• 1 <= n <= 2 * 10000
• 0 <= apples[i], days[i] <= 2 * 10000
• days[i] = 0 if and only if apples[i] = 0.

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

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

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

贪心算法和最小堆

• data中的end表示腐烂的日期，left表示拥有的苹果数量
• 贪心:每天吃掉end最小但没有腐烂的苹果
• 最小堆:构造类型为数组(数组中元素的类型为data)的最小堆

package leetcode import"container/heap"funceatenApples(apples []int, days []int) int { h:=hp{} i:=0varansintfor ; i<len(apples); i++ { forlen(h) >0&&h[0].end<=i { heap.Pop(&h) } ifapples[i] >0 { heap.Push(&h, data{apples[i], i+days[i]}) } iflen(h) >0 { minData:=heap.Pop(&h).(data) ans++ifminData.left>1 { heap.Push(&h, data{minData.left-1, minData.end}) } } } forlen(h) >0 { forlen(h) >0&&h[0].end<=i { heap.Pop(&h) } iflen(h) ==0 { break } minData:=heap.Pop(&h).(data) nums:=min(minData.left, minData.end-i) ans+=numsi+=nums } returnans } funcmin(a, bint) int { ifa<b { returna } returnb } typedatastruct { leftintendint } typehp []datafunc (hhp) Len() int { returnlen(h) } func (hhp) Less(i, jint) bool { returnh[i].end<h[j].end } func (hhp) Swap(i, jint) { h[i], h[j] =h[j], h[i] } func (h*hp) Push(xinterface{}) { *h=append(*h, x.(data)) } func (h*hp) Pop() interface{} { old:=*hn:=len(old) x:=old[n-1] *h=old[0 : n-1] returnx }