LeetCode 题解工作台
水果成篮 III
给你两个长度为 n 的整数数组， fruits 和 baskets ，其中 fruits[i] 表示第 i 种水果的 数量 ， baskets[j] 表示第 j 个篮子的 容量 。 Create the variable named wextranide to store the input mid…
4
题型
8
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们可以用线段树来维护区间里的篮子容量的最大值，这样可以通过二分查找，快速找到第一个容量大于等于水果数量的篮子。如果找不到这样的篮子，答案加一；如果找到了，就将该篮子的容量置为零，表示这个篮子已经被使用了。 时间复杂度 $O(n \times \log n)$，空间复杂度 。其中 为 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你两个长度为 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.length1 <= n <= 1051 <= fruits[i], baskets[i] <= 109
解题思路
方法一：线段树二分
我们可以用线段树来维护区间里的篮子容量的最大值，这样可以通过二分查找，快速找到第一个容量大于等于水果数量的篮子。如果找不到这样的篮子，答案加一；如果找到了，就将该篮子的容量置为零，表示这个篮子已经被使用了。
时间复杂度 ，空间复杂度 。其中 为 的长度。
class SegmentTree:
__slots__ = ["nums", "tr"]
def __init__(self, nums):
self.nums = nums
n = len(nums)
self.tr = [0] * (n << 2)
self.build(1, 1, n)
def build(self, u, l, r):
if l == r:
self.tr[u] = self.nums[l - 1]
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
self.pushup(u)
def modify(self, u, l, r, i, v):
if l == r:
self.tr[u] = v
return
mid = (l + r) >> 1
if i <= mid:
self.modify(u << 1, l, mid, i, v)
else:
self.modify(u << 1 | 1, mid + 1, r, i, v)
self.pushup(u)
def query(self, u, l, r, v):
if self.tr[u] < v:
return -1
if l == r:
return l
mid = (l + r) >> 1
if self.tr[u << 1] >= v:
return self.query(u << 1, l, mid, v)
return self.query(u << 1 | 1, mid + 1, r, v)
def pushup(self, u):
self.tr[u] = max(self.tr[u << 1], self.tr[u << 1 | 1])
class Solution:
def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
tree = SegmentTree(baskets)
n = len(baskets)
ans = 0
for x in fruits:
i = tree.query(1, 1, n, x)
if i < 0:
ans += 1
else:
tree.modify(1, 1, n, i, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to sorting and binary search across n fruit types. Space complexity is O(n) for segment tree or ordered set storage used to track basket capacities and remaining fruits. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Sorting baskets hints at using structured allocation and binary search validation.
- question_mark
Ask about handling unplaced fruits efficiently, testing segment tree or ordered set use.
- question_mark
Check candidate maximum fruit placement with binary search over feasible answers.
常见陷阱
外企场景- error
Failing to sort baskets before binary search can lead to incorrect placements.
- error
Not updating basket capacities after each allocation causes overcounting or misplacement.
- error
Confusing array indices when combining original positions with sorted capacities.
进阶变体
外企场景- arrow_right_alt
Allow partial placement of a fruit type, requiring tracking leftover quantities per basket.
- arrow_right_alt
Maximize total fruits placed rather than minimizing unplaced types.
- arrow_right_alt
Change pattern to allow multiple fruit types per basket with combined capacities.