水果入篮 III

题目描述

LeetCode 3479 — 水果入篮 III (Medium)

给定两个长度均为 n 的整数数组 fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的数量，baskets[j] 表示第 j 个篮子的容量。你需要从左到右依次处理每种水果：将 fruits[i] 放入第一个（最左边的）尚未使用且容量大于等于 fruits[i] 的篮子中。每个篮子最多只能装一种水果。如果找不到合适的篮子，该水果就无法放置。返回无法放置的水果种类数。

示例 1：

• 输入：fruits = [4, 2, 5], baskets = [3, 5, 4]
• 输出：1
• 解释：水果 4 放入篮子 5，水果 2 放入篮子 3，水果 5 无法放入篮子 4，未放置数为 1。

示例 2：

• 输入：fruits = [3, 6, 1], baskets = [6, 4, 7]
• 输出：0
• 解释：水果 3 放入篮子 6，水果 6 放入篮子 7，水果 1 放入篮子 4，全部放置成功。

约束：

• n == fruits.length == baskets.length
• 1 <= n <= 10^5
• 1 <= fruits[i], baskets[i] <= 10^9

---

求解思路：线段树

先说说线段树本身是什么。线段树是一棵二叉树，用于维护一个数组的区间信息——比如区间和、区间最大值、区间最小值等。它的核心思想是分治：把一个大区间不断对半拆分，直到每个子区间只包含一个元素，然后自底向上合并信息。建树时，每个叶子节点存储原数组的一个元素，内部节点存储其左右子区间的合并结果（比如维护最大值就是取左右子节点的较大者）。这样一棵树的高度是 O(log n)，单次区间查询或单点更新都可以在 O(log n) 时间内完成。

具体来说，线段树的节点用编号表示（根节点为 1，左子节点为 2*i，右子节点为 2*i+1），每个节点管辖原数组的一个连续区间 [start, end]。建树递归地把区间一分为二，叶子节点直接赋值，内部节点通过 pushUp 从左右子节点拉取信息。查询时，如果当前节点的区间完全落在查询范围内，直接返回该节点的值；否则递归查询左右子区间并合并结果。更新时，找到对应的叶子节点修改值，然后一路向上更新祖先节点。注释里的区间查询代码展示了标准的线段树查询流程，不过本题用到的是一个变体查询，稍后会讲。

回到这道题。题目的核心需求是：对每种水果，从左到右找到第一个容量足够且尚未使用的篮子。一个直观的做法是线性扫描篮子数组，找到第一个满足条件的篮子就标记为已用。但这样每种水果最多扫描 n 个篮子，总时间复杂度是 O(n²)，在 n = 10^5 的数据规模下会超时。

怎么加速这个"找第一个容量 >= x 的篮子"的过程？如果我们把篮子数组构建成一棵线段树，每个节点存储该区间内篮子的最大容量，那么就可以利用树的结构快速定位目标。具体来说，从根节点开始：如果左子区间的最大容量 >= x，说明左边一定有满足条件的篮子，优先往左走；否则往右走。走到叶子节点时，就找到了第一个满足条件的篮子。找到后，将该篮子的容量设为 -1（表示已使用），并沿路径向上更新祖先节点的最大值。这样，每次查询 + 更新的总开销是 O(log n)。

这个策略之所以正确，是因为线段树的节点编号遵循"左子节点编号更小"的规则，而编号更小意味着对应的原数组下标更靠左。所以优先走左子树，自然就找到了最左边的满足条件的篮子。如果左子区间的最大容量已经不够，就跳过整个左子树，去右边找——这比线性扫描逐个检查要高效得多。

---

解法：线段树

#include <vector>
#include <algorithm>
using namespace std;

class SegmentTree {
private:
    vector<int> tree; // 线段树数组，存储区间最大值
    int n;

    // 向上合并：当前节点的值 = max(左子节点, 右子节点)
    void pushUp(int node) {
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    // 递归建树
    void build(int node, int start, int end, const vector<int>& nums) {
        if (start == end) {
            tree[node] = nums[start]; // 叶子节点：直接赋值
            return;
        }
        int mid = start + (end - start) / 2;
        build(node * 2, start, mid, nums);           // 左子树
        build(node * 2 + 1, mid + 1, end, nums);     // 右子树
        pushUp(node); // 左右子树建好后，合并信息
    }

public:
    SegmentTree(const vector<int>& nums) {
        n = nums.size();
        if (n > 0) {
            tree.resize(4 * n, 0); // 线段树空间通常开 4 倍
            build(1, 0, n - 1, nums);
        }
    }

    // 将下标 idx 的值更新为 val
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (idx <= mid) update(node * 2, start, mid, idx, val);
        else update(node * 2 + 1, mid + 1, end, idx, val);
        pushUp(node);
    }

    // 查询第一个 >= x 的元素，找到后将其设为 -1，返回 1；未找到返回 -1
    int query(int node, int start, int end, int x) {
        if (tree[node] < x) return -1; // 当前区间最大值都不够，无解
        if (start == end) { // 到达叶子节点，找到目标
            update(1, 0, n - 1, start, -1); // 标记为已使用
            return 1;
        }
        int mid = start + (end - start) / 2;
        if (tree[node * 2] >= x) return query(node * 2, start, mid, x); // 优先走左子树
        return query(node * 2 + 1, mid + 1, end, x); // 左边不行，走右边
    }
};

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = baskets.size();
        SegmentTree tree(baskets);
        int ans = n;
        for (int i : fruits) {
            if (tree.query(1, 0, n - 1, i) == 1) ans--; // 放置成功，未放置数减一
        }
        return ans;
    }
};

复杂度： 时间 O(n log n)（n 次查询，每次 O(log n)）；空间 O(n)（线段树数组）。

---

相关题目

• LeetCode 307 — 区域和检索 - 数组可修改（线段树入门，单点更新 + 区间求和）
• LeetCode 315 — 计算右侧小于当前元素的个数（线段树统计逆序对）
• LeetCode 493 — 翻转对（线段树维护区间计数）
• LeetCode 218 — 天际线问题（线段树的经典应用）