- Leetcode 3479. Fruits Into Baskets III
- 1. 解题思路
- 2. 代码实现
- 题目链接：3479. Fruits Into Baskets III
1. 解题思路
这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。
因此，我们只需要将basket按照其capacity进行排序，此时，考察每一个水果时，我们用二分法即可快速找到某一个坐标idx满足其后任意一个箱子都可以用于盛放该水果。此时，我们就要从对应的这些篮子当中找到其原始的坐标最小的位置即可。而这就是一个典型的segment tree的问题了。
对于segment tree，网上已经有不少相关的介绍了，我自己也写过一篇小文章作为备忘（经典算法：Segment Tree），因此这里就不过多展开了，有兴趣的读者可以自行去了解一下。
2. 代码实现
给出python代码实现如下：
class SegmentTree:def __init__(self, arr):self.length = len(arr)self.tree = self.build(arr)def feature_func(self, *args):return min(args)def build(self, arr):n = len(arr)tree = [0 for _ in range(2*n)]for i in range(n):tree[i+n] = arr[i]for i in range(n-1, 0, -1):tree[i] = self.feature_func(tree[2*i], tree[2*i+1])return treedef update(self, idx, val):idx = idx + self.lengthself.tree[idx] = valwhile idx > 1:self.tree[idx // 2] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx = idx // 2returndef query(self, lb, rb):lb += self.length rb += self.lengthnodes = []while lb < rb:if lb % 2 == 1:nodes.append(self.tree[lb])lb += 1if rb % 2 == 0:nodes.append(self.tree[rb])rb -= 1lb = lb // 2rb = rb // 2if lb == rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)class Solution:def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:n = len(fruits)ordered_baskets = sorted([(cap, idx) for idx, cap in enumerate(baskets)])ordered_baskets_capacity = [x[0] for x in ordered_baskets]ordered_baskets_index = [x[1] for x in ordered_baskets]segment_tree = SegmentTree(ordered_baskets_index)ans = 0for fruit in fruits:idx = bisect.bisect_left(ordered_baskets_capacity, fruit)if idx >= n:ans += 1continueleft_most_avaliable = segment_tree.query(idx, n-1)if left_most_avaliable >= n:ans += 1continuebasket = (baskets[left_most_avaliable], left_most_avaliable)idx = bisect.bisect_left(ordered_baskets, basket)segment_tree.update(idx, n)return ans
提交代码评测得到：耗时2398ms，占用内存43.9MB。
