mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 09:23:19 +08:00
124 lines
3.6 KiB
Markdown
124 lines
3.6 KiB
Markdown
# [1705. Maximum Number of Eaten Apples](https://leetcode.com/problems/maximum-number-of-eaten-apples/)
|
||
|
||
## 题目
|
||
|
||
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)的最小堆
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
import "container/heap"
|
||
|
||
func eatenApples(apples []int, days []int) int {
|
||
h := hp{}
|
||
i := 0
|
||
var ans int
|
||
for ; i < len(apples); i++ {
|
||
for len(h) > 0 && h[0].end <= i {
|
||
heap.Pop(&h)
|
||
}
|
||
if apples[i] > 0 {
|
||
heap.Push(&h, data{apples[i], i + days[i]})
|
||
}
|
||
if len(h) > 0 {
|
||
minData := heap.Pop(&h).(data)
|
||
ans++
|
||
if minData.left > 1 {
|
||
heap.Push(&h, data{minData.left - 1, minData.end})
|
||
}
|
||
}
|
||
}
|
||
for len(h) > 0 {
|
||
for len(h) > 0 && h[0].end <= i {
|
||
heap.Pop(&h)
|
||
}
|
||
if len(h) == 0 {
|
||
break
|
||
}
|
||
minData := heap.Pop(&h).(data)
|
||
nums := min(minData.left, minData.end-i)
|
||
ans += nums
|
||
i += nums
|
||
}
|
||
return ans
|
||
}
|
||
|
||
func min(a, b int) int {
|
||
if a < b {
|
||
return a
|
||
}
|
||
return b
|
||
}
|
||
|
||
type data struct {
|
||
left int
|
||
end int
|
||
}
|
||
|
||
type hp []data
|
||
|
||
func (h hp) Len() int { return len(h) }
|
||
func (h hp) Less(i, j int) bool { return h[i].end < h[j].end }
|
||
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
|
||
|
||
func (h *hp) Push(x interface{}) {
|
||
*h = append(*h, x.(data))
|
||
}
|
||
|
||
func (h *hp) Pop() interface{} {
|
||
old := *h
|
||
n := len(old)
|
||
x := old[n-1]
|
||
*h = old[0 : n-1]
|
||
return x
|
||
}
|
||
``` |