【LeetCode】5638.吃苹果的最大数目

题目链接

5638. 吃苹果的最大数目

题目描述

解题思路

贪心+优先队列

就和平时吃零食一样,优先把快过期的零食吃完,同理,在本题中优先吃那些即将过期的苹果.

如何才能知道现在那些苹果最快就要过期,这些快要过期的苹果又还剩余几个呢??

利用优先队列,队列中存储的就是一个二维数组,[苹果数目,苹果过期时间].

AC代码

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        Queue<int[]> q = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] i1,int[] i2){
                return i1[1] - i2[1];
            }
        });
        int ans = 0;
        for(int i = 0; i < apples.length; i++){
            //1.清理苹果剩余为0以及过期苹果
            while(!q.isEmpty()){
                int[] temp = q.peek();
                if(temp[0] <= 0 || temp[1] < i){
                    q.poll();
                }else break;
            }
            //2.添加当天新长出的苹果,如果当天苹果数为0,则跳过
            if(apples[i] > 0){
                int pair[] = new int[2];
                pair[0] = apples[i];
                pair[1] = i + days[i] - 1;
                q.offer(pair);
            }
            //3.优先吃最早过期的.
            int temp[] = q.peek();
            if(temp != null){
                temp[0]--;
                ans++;  
            }
        }
        //优先队列中还存在着元素,接着吃苹果.value代表当前天数
        int value = apples.length;
        while(!q.isEmpty()){
            int temp[] = q.peek();
            if(temp[0] == 0 || temp[1] < value){
                q.poll();
            }else{
                temp[0]--;
                ans++;
                value++;
            } 
        }
        return ans;
    }
}