LeetCode 1705. 吃苹果的最大数目

2026-09-13 HGNULB 约 5 分钟

文章信息 2 个分类 3 个标签

分类

LeetCode 中等

题目描述

✅ 1705. 吃苹果的最大数目

题意分析

第 i 天长出 apples[i] 个苹果，这一批在第 i + days[i] 天开始腐烂，到期当天已经不能吃。每天最多吃一个苹果，求最终能够吃掉的最大数量。

苹果停止生长后，库存只要没有过期仍可继续吃。不同批次有各自到期日和数量，不能只按生长先后处理，也不是只计算前 n 天的食用量。

解法：按最早到期贪心，生长结束后批量消耗

核心思路

[!blue]

每天有可食用苹果时，优先选择最早到期的那一批。若某个方案今天吃晚到期苹果、以后某天才吃早到期苹果，将两次选择交换后，早到期苹果今天仍有效，晚到期苹果在原来吃早到期苹果的那天也不会过期，数量不会减少。若早到期苹果原计划不吃，直接替换今天的选择也不减数量。

用最小堆按到期日保存 (到期日, 剩余数量)。生长期每天先加入新批次，再移除堆顶已经到期或耗尽的批次；堆仍非空时，就吃堆顶一个。减少的是数量，到期日没有变化，因此堆的优先顺序不需要重新调整。

生长还没结束时，不能一次连续吃完当前批次，因为明天可能到达更早过期的新批次。必须逐日加入新资源，再重新选择最紧急的苹果。

生长期结束后不再有新批次进入，当前堆顶持续是最早到期的剩余批次，可以批量计算。从当前日 day 到到期日之前，一共有 expires - day 个可食用日期，能吃的数量为 min(剩余数量, expires - day)。把答案与日期同时增加这么多，再处理下一个批次。

如果这一批先耗尽，就继续取下一批；如果时间先到期，吃不完的部分已经无法挽救，可以随弹出的批次丢弃。日期推进可能让其他批次也过期，因此每次取出后仍要检查到期日。

解题步骤

生长期逐日处理，存在有效苹果时将该日批次按到期日加入最小堆。

连续移除到期日不晚于当天、或剩余数量为零的堆顶。

堆非空则消费最早到期批次的一个苹果，累计答案。

生长期结束后，逐个弹出最早到期批次，过期则跳过。

对有效批次批量吃掉数量与剩余可用天数的较小值，同时推进日期，直到堆空。

代码实现

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int day = 0;
        int answer = 0;

        for (; day < apples.length; day++) {
            if (apples[day] > 0 && days[day] > 0) {
                heap.add(new int[] {
                    day + days[day],
                    apples[day]
                });
            }

            while (!heap.isEmpty() && (heap.peek()[0] <= day || heap.peek()[1] == 0)) {
                heap.remove();
            }

            if (!heap.isEmpty()) {
                heap.peek()[1]--;
                answer++;
            }
        }

        while (!heap.isEmpty()) {
            int[] batch = heap.remove();

            if (batch[0] <= day) {
                continue;
            }

            int eat = Math.min(batch[1], batch[0] - day);

            answer += eat;
            day += eat;
        }

        return answer;
    }
}

import "container/heap"

type appleBatch struct{ expires, count int }
type appleHeap []appleBatch

func (h appleHeap) Len() int { return len(h) }

func (h appleHeap) Less(i, j int) bool { return h[i].expires < h[j].expires }

func (h appleHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *appleHeap) Push(x any) { *h = append(*h, x.(appleBatch)) }

func (h *appleHeap) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

func eatenApples(apples, days []int) int {
    h := appleHeap{}
    day, answer := 0, 0
    for ; day < len(apples); day++ {
        if apples[day] > 0 && days[day] > 0 {
            heap.Push(&h, appleBatch{day + days[day], apples[day]})
        }
        for len(h) > 0 && (h[0].expires <= day || h[0].count == 0) {
            heap.Pop(&h)
        }
        if len(h) > 0 {
            h[0].count--
            answer++
        }
    }
    for len(h) > 0 {
        batch := heap.Pop(&h).(appleBatch)
        if batch.expires <= day {
            continue
        }
        eat := min(batch.count, batch.expires-day)
        answer += eat
        day += eat
    }
    return answer
}

复杂度分析

时间复杂度：$O(n\log(n+1))$，最多加入 n 个批次，每个批次最多弹出一次；生长期处理 n 天，结束后按批次推进，不逐日遍历剩余保鲜期。

空间复杂度：$O(n)$，堆最多保存所有尚未清理的批次，每个批次只记录到期日与剩余数量。

关键点总结

[!green]

最早到期优先可由食用顺序交换证明，不会减少最终数量。

到期日是不能食用的第一天，比较与剩余天数都按这个边界计算。

生长期逐日接收新批次，结束后才允许按最早到期批次跨多天处理。

堆只按到期日排序，原地减少剩余数量不破坏堆性质。

易错点总结

[!yellow]

将清理条件写成到期日小于当天，到期当天的腐烂苹果会被多吃一次。

把剩余可食用天数算成 expires - day + 1，错误包含到期日。

按最早生长或剩余数量最多选择，不能保证先保护最早失效的食用机会。

生长期直接连续消费一个批次，会跳过未来新批次的比较，可能浪费更早到期的苹果。

生长结束立即返回，遗漏之后仍能食用的库存。

批量增加答案却没有同步推进日期，后面的批次会重复使用同一批日子。

相似题目

题目	难度	关联与区别
1353. 最多可以参加的会议数目	中等	都利用最早截止时间贪心，并且每个时刻只能处理一个对象；本题同一批次可含多个苹果。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/82919856

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！