把箱子放进仓库里 II
难度:
标签:
题目描述
代码结果
运行时间: 109 ms, 内存: 33.7 MB
/*
* 思路:
* 1. 先对箱子和仓库的高度进行排序。
* 2. 从仓库的右边开始放箱子,尝试将尽量大的箱子放入仓库。
* 3. 如果当前箱子可以放入仓库(即箱子高度小于等于仓库高度),则计数增加。
*/
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
// 使用Java Stream API
Arrays.sort(boxes);
int[] warehouseSorted = Arrays.stream(warehouse)
.boxed()
.sorted(Collections.reverseOrder())
.mapToInt(Integer::intValue)
.toArray();
int boxIndex = boxes.length - 1;
int count = 0;
for (int space : warehouseSorted) {
if (boxIndex >= 0 && boxes[boxIndex] <= space) {
count++;
boxIndex--;
}
}
return count;
}
}
解释
方法:
这个题解采用了双指针和贪心算法的结合来解决问题。首先对箱子的尺寸进行排序,然后使用两个指针i和j分别指向仓库的左端和右端。算法从两边向中间扫描,尝试放置尽可能大的箱子。每次迭代中,首先找到两个指针位置中仓库的最大高度,然后比较这个高度和最大箱子的尺寸。如果最大箱子不能放入,则将其从列表中移除。如果能放入,根据仓库的高度决定是移动左指针还是右指针,以尽可能利用仓库的空间。这样直到箱子放完或者扫描完仓库的所有位置。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中,为什么需要先对箱子尺寸进行排序?排序的目的和对算法效率的影响是什么?
▷🦆
在决定移动左指针还是右指针时,为什么根据仓库的高度而不是其他因素决定?
▷🦆
题解中提到将不能放入的最大箱子移除,这一步是否可能导致其他较小的箱子也无法被放入仓库?
▷🦆
在仓库的高度差异大时,这种双指针和贪心算法的结合方式仍然适用吗?
▷