2025-09-09：水果成篮Ⅲ。用go语言，给你两个等长的整数数组 fruits 和 baskets：fruits[i] 表示第 i 类水果的数量，baskets[j] 表示第 j 个篮子的容量。按 fruits 的索引从小到大依次处理每一类水果：对于当前水果，找出下标最小且尚未被占用、容量不少于该水果数量的篮子，把这类水果放入；每个篮子最多放一种水果；若不存在符合条件的空篮子，则该类水果保持未放置。所有水果处理完后，返回仍然未被放入任何篮子的水果种类数。

n == fruits.length == baskets.length。

1 <= n <= 100000。

1 <= fruits[i], baskets[i] <= 1000000000。

输入： 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。

题目来自力扣3479。

分步骤描述过程

1. 初始化：

   • 首先，检查篮子数组 baskets 的长度。如果长度为0（即没有篮子），则所有水果都无法放置，直接返回水果的种类数（即 len(fruits)）。
   • 否则，初始化一个线段树（SegTree）结构，用于高效地查询和更新篮子的状态。线段树节点数组 segNode 的大小为 4 * m + 7（其中 m 是篮子的数量），篮子数组 baskets 被存储在线段树中。

2. 构建线段树：

   • 线段树构建函数 build 被调用，递归地将篮子数组构建成线段树。每个叶子节点存储对应篮子的容量，内部节点存储其左右子树的最大值（即区间内的最大篮子容量）。

3. 处理每类水果：

   • 遍历每类水果（按索引从小到大）：
     • 对于当前水果 fruits[i]，使用二分查找（在线段树上）寻找下标最小的、容量不小于 fruits[i] 且尚未被占用的篮子。
       • 二分查找的区间为 [0, m-1]（即所有篮子）。
       • 对于每个中间位置 mid，查询线段树区间 [0, mid] 的最大值。如果该最大值大于等于当前水果的数量，说明存在符合条件的篮子（且下标最小的在左半部分），继续在左半部分查找；否则在右半部分查找。
     • 如果找到了这样的篮子（res != -1）并且该篮子的容量确实大于等于水果数量（实际上通过线段树查询已经保证了这一点），则将该篮子标记为已被占用（通过线段树更新将该篮子的容量设置为 INT_MIN，这样后续查询就不会再找到它）。
     • 如果没有找到符合条件的篮子，则未放置的水果种类数 count 加1。

4. 返回结果：

   • 处理完所有水果后，返回未放置的水果种类数 count。

总的时间复杂度和总的额外空间复杂度

• 时间复杂度：

  • 构建线段树：O(m)，其中 m 是篮子的数量。
  • 处理每类水果：对于每类水果，进行二分查找（每次二分查找需要 O(log m) 时间），每次二分查找中需要在线段树上查询（每次查询也是 O(log m) 时间），并且如果找到篮子还需要更新线段树（一次更新也是 O(log m) 时间）。因此处理每类水果的总时间是 O(log² m)（因为二分查找和线段树操作都是对数时间）。
  • 总共有 n 类水果，所以总时间复杂度为 O(n * log² m)。由于 n 和 m 等长（题目中 n == m），所以可以表示为 O(n * log² n)。

• 额外空间复杂度：

  • 线段树需要 O(m) 的额外空间（即 4 * m + 7），因此额外空间复杂度为 O(m)。由于 m = n，所以为 O(n)。

总结：

• 时间复杂度：O(n * log² n)
• 额外空间复杂度：O(n)

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

const (
	INT_MIN = math.MinInt32
)

type SegTree struct {
	segNode []int
	baskets []int
}

func (this *SegTree) build(p, l, r int) {
	if l == r {
		this.segNode[p] = this.baskets[l]
		return
	}
	mid := (l + r) >> 1
	this.build(p<<1, l, mid)
	this.build(p<<1|1, mid+1, r)
	this.segNode[p] = max(this.segNode[p<<1], this.segNode[p<<1|1])
}

func (this *SegTree) query(p, l, r, ql, qr int) int {
	if ql > r || qr < l {
		return INT_MIN
	}
	if ql <= l && r <= qr {
		return this.segNode[p]
	}
	mid := (l + r) >> 1
	return max(this.query(p<<1, l, mid, ql, qr),
		this.query(p<<1|1, mid+1, r, ql, qr))
}

func (this *SegTree) update(p, l, r, pos, val int) {
	if l == r {
		this.segNode[p] = val
		return
	}
	mid := (l + r) >> 1
	if pos <= mid {
		this.update(p<<1, l, mid, pos, val)
	} else {
		this.update(p<<1|1, mid+1, r, pos, val)
	}
	this.segNode[p] = max(this.segNode[p<<1], this.segNode[p<<1|1])
}

func numOfUnplacedFruits(fruits []int, baskets []int) int {
	m := len(baskets)
	if m == 0 {
		return len(fruits)
	}

	tree := SegTree{
		segNode: make([]int, 4*m+7),
		baskets: baskets,
	}
	tree.build(1, 0, m-1)

	count := 0
	for i := 0; i < len(fruits); i++ {
		l, r, res := 0, m-1, -1
		for l <= r {
			mid := (l + r) >> 1
			if tree.query(1, 0, m-1, 0, mid) >= fruits[i] {
				res = mid
				r = mid - 1
			} else {
				l = mid + 1
			}
		}
		if res != -1 && tree.baskets[res] >= fruits[i] {
			tree.update(1, 0, m-1, res, INT_MIN)
		} else {
			count++
		}
	}

	return count
}

func main() {
	fruits := []int{4, 2, 5}
	baskets := []int{3, 5, 4}
	result := numOfUnplacedFruits(fruits, baskets)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import sys

INT_MIN = -2**31

class SegTree:
    def __init__(self, baskets):
        self.baskets = baskets
        self.n = len(baskets)
        self.seg = [INT_MIN] * (4 * self.n + 7)
        if self.n > 0:
            self.build(1, 0, self.n - 1)

    def build(self, p, l, r):
        if l == r:
            self.seg[p] = self.baskets[l]
            return
        mid = (l + r) // 2
        self.build(p * 2, l, mid)
        self.build(p * 2 + 1, mid + 1, r)
        self.seg[p] = max(self.seg[p * 2], self.seg[p * 2 + 1])

    def query(self, p, l, r, ql, qr):
        if ql > r or qr < l:
            return INT_MIN
        if ql <= l and r <= qr:
            return self.seg[p]
        mid = (l + r) // 2
        return max(self.query(p * 2, l, mid, ql, qr),
                   self.query(p * 2 + 1, mid + 1, r, ql, qr))

    def update(self, p, l, r, pos, val):
        if l == r:
            self.seg[p] = val
            return
        mid = (l + r) // 2
        if pos <= mid:
            self.update(p * 2, l, mid, pos, val)
        else:
            self.update(p * 2 + 1, mid + 1, r, pos, val)
        self.seg[p] = max(self.seg[p * 2], self.seg[p * 2 + 1])


def numOfUnplacedFruits(fruits, baskets):
    m = len(baskets)
    if m == 0:
        return len(fruits)

    tree = SegTree(baskets)
    count = 0

    for f in fruits:
        l, r, res = 0, m - 1, -1
        # 在前缀 [0, mid] 上二分查找第一个有足够容量的位置
        while l <= r:
            mid = (l + r) // 2
            if tree.query(1, 0, m - 1, 0, mid) >= f:
                res = mid
                r = mid - 1
            else:
                l = mid + 1
        if res != -1 and tree.baskets[res] >= f:
            # 标记该篮子为已用（在线段树中设为很小的值）
            tree.update(1, 0, m - 1, res, INT_MIN)
        else:
            count += 1

    return count

if __name__ == "__main__":
    fruits = [4, 2, 5]
    baskets = [3, 5, 4]
    print(numOfUnplacedFruits(fruits, baskets))