3479. 水果成篮 III

Problem: 3479. 水果成篮 III

思路

线段树和二分思想，线段树维护baskets区间最大值，枚举fruits中的水果。

解题过程

• 如果根节点（树的最大容量）小于fruits[i]，表示没有这样大的篮子，返回-1。
• 否则先递归左子树，再递归右子树，找到返回当前位置。
• 找到需要更新线段树。

复杂度

• 时间复杂度: $O(nlogn)$
• 空间复杂度: $O(n)$

Code

class SegmentTree {
private:vector<int> maxTree; // 存储每个区间最大容量vector<bool> used;   // 标记区间是否完全被使用int n;               // 篮子的数量void build(int node, int start, int end, const vector<int>& baskets) {if (start == end) {                 // 叶子节点maxTree[node] = baskets[start]; // 最大容量等于该处篮子容量used[node] = false;             // 初始未使用return;}int mid = (start + end) / 2;build(2 * node, start, mid, baskets);       // 构建左子树build(2 * node + 1, mid + 1, end, baskets); // 构建右子树// 当前节点的最大容量是左右子树最大容量的最大值maxTree[node] = max(maxTree[2 * node], maxTree[2 * node + 1]);used[node] = false;}int query(int node, int start, int end, int val, int& pos) {// 区间完全使用或最大容量小于该种水果的数量if (used[node] || maxTree[node] < val)return -1;if (start == end) { // 叶子节点// 记录找到篮子的位置pos = start;return pos;}int mid = (start + end) / 2;// 查询左子树int leftPos = -1;if (query(2 * node, start, mid, val, leftPos) != -1) {pos = leftPos;return pos;}// 查询右子树int rightPos = -1;if (query(2 * node + 1, mid + 1, end, val, rightPos) != -1) {pos = rightPos;return pos;}return -1; // 整个区间无符合条件的篮子}void update(int node, int start, int end, int idx) {if (start == end) {     // 到达叶子节点maxTree[node] = -1; // 标记为已使用used[node] = true;  // 标记为已使用return;}// 递归更新子节点int mid = (start + end) / 2;if (idx <= mid) {update(2 * node, start, mid, idx);} else {update(2 * node + 1, mid + 1, end, idx);}// 更新父节点状态maxTree[node] = max(maxTree[2 * node], maxTree[2 * node + 1]);used[node] = (maxTree[2 * node] == -1 && maxTree[2 * node + 1] == -1);}public:SegmentTree(const vector<int>& baskets) {n = baskets.size();maxTree.resize(4 * n);used.resize(4 * n, false);build(1, 0, n - 1, baskets);}int findAndMark(int val) {int pos = -1;if (query(1, 0, n - 1, val, pos) != -1) {update(1, 0, n - 1, pos);return pos;}return -1;}
};class Solution {
public:int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {SegmentTree st(baskets);int unplaced = 0;for (int f : fruits) {if (f == 0)continue;if (st.findAndMark(f) == -1) {unplaced++;}}return unplaced;}
};