把箱子放进仓库里 I
难度:
标签:
题目描述
代码结果
运行时间: 92 ms, 内存: 35.0 MB
/*
* 思路:
* 1. 使用流来简化数组操作
* 2. 计算每个仓库位置的最大可容纳高度
* 3. 将箱子排序,并从末尾开始尝试放入仓库
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class BoxInWarehouseStream {
public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
int[] minHeight = IntStream.range(0, warehouse.length)
.map(i -> IntStream.range(0, i + 1)
.map(j -> warehouse[j])
.min()
.getAsInt())
.toArray();
Arrays.sort(boxes);
int count = 0;
int i = warehouse.length - 1;
for (int j = 0; j < boxes.length && i >= 0; i--) {
if (boxes[j] <= minHeight[i]) {
count++;
j++;
}
}
return count;
}
}
解释
方法:
首先对箱子的尺寸进行排序,以确保可以尽可能地将更小的箱子放入仓库中。然后遍历仓库的每个位置,对于每个位置,检查当前最大的箱子是否可以放入(由于已经排过序,所以当前最大的箱子是未被放置的最大箱子)。如果不能放入,则继续检查下一个较小的箱子。如果可以放入,则将该箱子放入仓库,并继续检查下一个仓库的位置。这种方法利用了贪心的策略,旨在每个仓库位置尽可能放入最大的箱子,直到无法放入更多箱子为止。
时间复杂度:
O(n log n + n + m) 或简化为 O(n log n + m)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在解决这个问题时选择使用贪心算法?贪心算法在这种场景下是否总是能得到最优解?
▷🦆
你如何处理仓库中高度不一的问题?在代码中似乎没有明显处理不同高度的逻辑。
▷🦆
在确定不能放入更大箱子后,直接尝试下一个较小的箱子是否可能错过某些特殊情况下的最佳放置策略?
▷🦆
在实现中,一旦遇到无法放入的箱子就中断循环,这种处理方式是否可能导致不是所有有效的仓库位置都被检查?
▷