力扣3074重新分装苹果的题解

题目：

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

我的代码：class Solution {
public int minimumBoxes(int[] apple, int[] capacity) {
int sum=0;//总质量
// int count=0;//计算所需要箱子的数量
for(int i=0;i<apple.length;i++){//计算n个苹果的质量
sum+=apple[i];
}
if(sum==0) return 0;
for(int i=0;i<capacity.length-1;i++){//降序的冒泡排序 排序的轮数
for(int j=0;j<capacity.length-i-1;j++){//最大的元素在前面
if(capacity[j]<capacity[j+1]){
int temp=capacity[j];
capacity[j]=capacity[j+1];
capacity[j+1]=temp;
}
}
}
int[] prefix;//前缀和数组
prefix=new int[capacity.length+1];
for(int i=1;i<=capacity.length;i++){//构建前缀和数组
prefix[i]=prefix[i-1]+capacity[i-1];
}
for(int i=1;i<=capacity.length;i++){
if(prefix[i]>=sum){
return i;
}
}
return capacity.length;//理论上不会出现
}
}

对题目的理解：我们要首先去计算苹果有多重，且对capacity数组进行处理，我用的冒泡排序进行降序处理，因为我们要使箱子的数量最少，所以应该先用能装最多的箱子去装苹果，因此可以获得最少的箱子树。

在这代码中我还用了前缀和去计算装苹果的重量，还有一种极端的情况是最后的return语句，用所有的箱子。