题解 | #苹果树#

题意整理

• 有n颗苹果树，每棵树上有对应的果子存在数组a。
• 数组b中存放着每天计划采摘的果子，如果某棵树上不足对应的果子，则全部摘完。
• 求每天供应的苹果数。

方法一（暴力法）

1.解题思路

直接遍历每棵树上还剩下的果子数，如果有个，则直接摘个，如果没有，则摘剩下的对应果子数。然后每次都把所有树上摘下的果子数累加放到结果数组。由于每次都要重新遍历a数组，时间开销过大，运行会超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型一维数组
     */
    public long[] solve (int[] a, int[] b) {
        int m=b.length;
        int n=a.length;
        //结果数组
        long[] res=new long[m];

        for(int i=0;i<m;i++){
            long fruit=0;
            for(int j=0;j<n;j++){
                //如果还有b[i]个，直接加b[i]个
                if(a[j]>=b[i]){
                    fruit+=b[i];
                    a[j]-=b[i];
                }
                //如果不足b[i]个，则加剩下的a[j]个
                else{
                    fruit+=a[j];
                    a[j]=0;
                }
            }
            res[i]=fruit;
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：循环体需要遍历次，所以最终的时间复杂度是。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度是。

方法二（小顶堆）

1.解题思路

可以考虑将所有树对应的果子放到一个小顶堆里，然后设置一个变量k用于统计每天每棵树累计采摘的果子数，如果堆顶元素小于等于k，说明对应树上的果子摘完了，从堆顶弹出，同时减去多摘的果子数。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型一维数组
     */
    public long[] solve (int[] a, int[] b) {
        //初始化结果集
        int m=b.length;
        int n=a.length;
        long[] res=new long[m];

        //初始化小顶堆
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int aa:a){
            queue.offer(aa);
        }

        //记录每棵树累计采摘的果子
        int k=0;
        for(int i=0;i<m;i++){
            k+=b[i];
            res[i]+=b[i]*queue.size();
            //如果堆顶元素小于等于k，说明对应树上的果子摘完了，需要移走
            while(!queue.isEmpty()&&k>=queue.peek()){
                //减去可能多计算的果子数
                res[i]-=(k-queue.poll());
            }

        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：a数组中元素入堆的时间复杂度是，最多弹出n个元素，所以弹出得时间复杂度也是，遍历b数组的时间复杂度是，所以最终的时间复杂度是。
• 空间复杂度：需要额外大小为n的小顶堆，所以空间复杂度是。