---
# System prepended metadata

title: 1705. Maximum Number of Eaten Apples
tags: [Leetcode, Priority Queue, Medium, Greedy]

---

# 1705. Maximum Number of Eaten Apples
###### tags: `Leetcode` `Medium` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/maximum-number-of-eaten-apples/
## 思路 $O(NlogN)$ $O(N)$
priorityqueue第一位存rot days, 第二位存有多少苹果, 每次吃rot day最接近的那个
遍历完array之后对于queue里面剩下的还没过期的苹果，为了加快计算速度，可以直接在ans和currday上+```Math.min(pq.peek()[0]-curr, pq.peek()[1])```
## Code
```java=
class Solution {
    public int eatenApples(int[] apples, int[] days) {
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        int ans = 0;
        for(int i=0; i<apples.length; i++){
            if(apples[i]!=0) pq.add(new int[]{i+days[i], apples[i]});
            while(!pq.isEmpty() && pq.peek()[0]<=i){
                pq.poll();
            }
            if(!pq.isEmpty()){
                ans++;
                pq.peek()[1]--;
                if(pq.peek()[1]==0) pq.poll();
            }
        }
        int curr = apples.length;
        while(!pq.isEmpty()){
            while(!pq.isEmpty() && pq.peek()[0]<=curr){
                pq.poll();
            }
            if(!pq.isEmpty()){
                int eatApples = Math.min(pq.peek()[0]-curr, pq.peek()[1]);
                ans += eatApples;
                curr += eatApples;
                pq.poll();
            }
        }
        return ans;
    }
}
```