水果成篮III

题目链接：https://leetcode.cn/problems/fruits-into-baskets-iii/description/?envType=daily-question&envId=2025-08-06

题目

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

• 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
• 每个篮子只能装 一种 水果。
• 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

分析

一开始我是这么做的

/**
 * @param {number[]} fruits
 * @param {number[]} baskets
 * @return {number}
 */
var numOfUnplacedFruits = function(fruits, baskets) {
    let result = fruits.length;
    for(let i = 0;i < fruits.length;i++){
        for(let j = 0;j < baskets.length;j++){
            if(fruits[i] <= baskets[j]){
                result--;
                baskets[j] = -1;
                break;
            }
        }
    }

    return result
};

但是由于我们的数据非常大，导致超出了时间限制，因此需要使用分块的方法进行优化。

块状分块优化思想（Block Decomposition）：

• 把 baskets 分块，每块大小大约是 √n；
• 每块维护一个 该块中未用篮子的最大容量，存在 maxV 数组中；
• 遍历每个水果时，先通过 maxV 快速排除无法满足的分块，缩小搜索范围；
• 一旦找到可以放水果的篮子，就标记为已用（设置为 0），并更新对应分块的最大值。

我们枚举 fruits 中的每一种水果，然后遍历每个块，会出现以下两种情况：

• 遍历到某个块的时候，当前块的最大值 maxV 小于当前水果的容量，那么说明当前块中没有容量大于当前水果数量的篮子，继续遍历下一个块。
• 遍历到某个块的时候，当前块的最大值 maxV 大于等于当前水果的容量，那么说明当前块中存在容量大于等于当前水果数量的篮子。此时从左到右遍历当前块中的每个篮子，如果当前篮子容量大于等于当前水果数量，那么将当前篮子容量置为 0，标记为已被该种水果占用，后续无法再使用。同时需要更新当前块的最大值 maxV，如果不更新最大值，可能会出现性能损耗，甚至是逻辑错误。

代码

/**
 * @param {number[]} fruits
 * @param {number[]} baskets
 * @return {number}
 */
var numOfUnplacedFruits = function(fruits, baskets) {
    const n = baskets.length;
    const m = Math.floor(Math.sqrt(n));
    const section = Math.ceil(n / m);
    let count = 0;
    const maxV = new Array(section).fill(0);

    for(let i = 0;i < n;i++){
        const sec = Math.floor(i / m);
        maxV[sec] = Math.max(maxV[sec], baskets[i]);
    }

    for(const fruit of fruits){
        let unset = 1;
        for(let sec = 0;sec < section;sec++){
            if(maxV[sec] < fruit){
                continue;
            }
            let choose = 0;
            maxV[sec] = 0;
            for(let i = 0;i < m;i++){
                const pos = sec * m + i;
                if (pos < n && baskets[pos] >= fruit && !choose) {
                    baskets[pos] = 0;
                    choose = 1;
                }
                if (pos < n) {
                    maxV[sec] = Math.max(maxV[sec], baskets[pos]);
                }
            }
            unset = 0;
            break;
        }
        count += unset;
    }
    return count;
};