目标
给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。
你需要对 fruits 数组从左到右按照以下规则放置水果：
- 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
- 每个篮子只能装 一种 水果。
- 如果一种水果 无法放入 任何篮子，它将保持 未放置。
返回所有可能分配完成后，剩余未放置的水果种类的数量。
示例 1
输入： fruits = [4,2,5], baskets = [3,5,4]
输出： 1
解释：
fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。示例 2
输入： fruits = [3,6,1], baskets = [6,4,7]
输出： 0
解释：
fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。说明：
- n == fruits.length == baskets.length
- 1 <= n <= 10^5
- 1 <= fruits[i], baskets[i] <= 10^9
思路
有水果 fruits 与 篮子 baskets 两个数组，fruits[i] 表示下标为 i 的水果数量，baskets[i] 表示下标为 i 位置上篮子的容量。现在需要按 fruits 的顺序从左往右将其放入篮子中，放置的位置是第一个能够容下水果的篮子，每个篮子只能放一种水果，如果没有位置能放下则保持未放置状态，求剩余未放置的水果种类。
暴力解法是枚举每种水果数量，然后枚举篮子，标记第一个能放下的篮子，时间复杂度为 O(n^2)。由于 basket 是无序的，没办法使用二分查找，并且排序会影响最终结果。因为未排序前，数量小的水果可能占据了大的篮子，导致数量多的水果无法放置。
考虑将 basket 分块，记录每一块的最大值，然后找到块内第一个大于 fruits[i] 的元素，然后将其置零。
代码
/**
* @date 2025-08-05 15:20
*/
public class NumOfUnplacedFruits3479 {
public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
int n = fruits.length;
int blockSize = (int) Math.ceil(Math.sqrt(n));
int m = (int) Math.ceil((double) n / blockSize);
int[] block = new int[m];
int bi = 0;
while (bi < m) {
int start = bi * blockSize;
int max = 0;
for (int j = start; j < start + blockSize && j < n; j++) {
max = Math.max(max, baskets[j]);
}
block[bi++] = max;
}
int res = n;
for (int fruit : fruits) {
int i = 0;
for (; i < m; i++) {
if (fruit <= block[i]) {
res--;
break;
}
}
int start = i * blockSize;
int newMax = 0;
for (int j = start; j < start + blockSize && j < n; j++) {
if (baskets[j] >= fruit) {
if (baskets[j] == block[i]) {
for (int k = j + 1; k < start + blockSize && k < n; k++) {
newMax = Math.max(newMax, baskets[k]);
}
block[i] = newMax;
}
baskets[j] = 0;
break;
} else {
newMax = Math.max(newMax, baskets[j]);
}
}
}
return res;
}
}
性能
