刷题记录帖子

LC. 3502. Minimum Cost to Reach Every Position

You are given an integer array cost of size n. You are currently at position n (at the end of the line) in a line of n + 1 people (numbered from 0 to n).

You wish to move forward in the line, but each person in front of you charges a specific amount to swap places. The cost to swap with person i is given by cost[i].

You are allowed to swap places with people as follows:

If they are in front of you, you must pay them cost[i] to swap with them.
If they are behind you, they can swap with you for free.
Return an array answer of size n, where answer[i] is the minimum total cost to reach each position i in the line.



Example 1:

Input: cost = [5,3,4,1,3,2]

Output: [5,3,3,1,1,1]

Explanation:

We can get to each position in the following way:

i = 0. We can swap with person 0 for a cost of 5.
i = 1. We can swap with person 1 for a cost of 3.
i = 2. We can swap with person 1 for a cost of 3, then swap with person 2 for free.
i = 3. We can swap with person 3 for a cost of 1.
i = 4. We can swap with person 3 for a cost of 1, then swap with person 4 for free.
i = 5. We can swap with person 3 for a cost of 1, then swap with person 5 for free.
Example 2:

Input: cost = [1,2,4,6,7]

Output: [1,1,1,1,1]

Explanation:

We can swap with person 0 for a cost of 1, then we will be able to reach any position i for free.



Constraints:

1 <= n == cost.length <= 100
1 <= cost[i] <= 100

核心本质（破局点）：
假设你想去位置 i，你有两种选择：

直接花钱：直接支付 cost[i] 和 i 交换。

“白嫖”策略（曲线救国）：你可以先花钱和位置更靠前的某个人 j（即 j < i）交换。交换完之后，你在位置 j，此时目标位置 i 就在你的后面了！根据规则，和后面的人换是免费的。所以，总共只需花费 cost[j]。

结论：到达位置 i 的最小成本，其实就是它前面所有人的成本以及它自己成本里的最小值。
数学表达：ans[i] = min(cost[0], cost[1], ..., cost[i])。

这也就是所谓的 前缀最小值 (Prefix Minimum) 模型。你的代码完美契合了这个模型！

1. class Solution:
   
2.     def minCosts(self, cost: List[int]) -> List[int]:
   
3.         leftSmallest = float('inf')
   
4. 
   
5.         ans = []
   
6. 
   
7.         for c in cost:
   
8.             if c >= leftSmallest:
   
9.                 ans.append(leftSmallest)
   
10.             else:
    
11.                 ans.append(c)
    
12.                 leftSmallest = c
    
13. 
    
14.         return ans

复制代码

一个简单的优化，用 min 来取代 if-else

1. class Solution:
   
2.     def minCosts(self, cost: List[int]) -> List[int]:
   
3.         min_cost = float('inf') # 维护当前遇到的最小代价
   
4.         ans = []
   
5.         
   
6.         for c in cost:
   
7.             # 更新当前的最小代价
   
8.             min_cost = min(min_cost, c)
   
9.             ans.append(min_cost)
   
10.             
    
11.         return ans

复制代码

LC. 3498. Reverse Degree of a String

简单题直接做

1. class Solution:
   
2.     def reverseDegree(self, s: str) -> int:
   
3.         ans = 0
   
4. 
   
5.         for i in range(len(s)):
   
6.             ans += ( i + 1) * (ord('z') - ord(s[i]) + 1)
   
7.         
   
8.         return ans
   
9.         

复制代码

LC 3492. Maximum Containers on a Ship

简单题，直接木桶原理，算最短的那个限制。

1. class Solution:
   
2.     def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
   
3.         return min(n * n, maxWeight // w)
   
4.         

复制代码

LC. 3491. Phone Number Prefix

数量级不大，所以可以直接暴力做。

就是一点需要注意是前缀要用 startswith，而不是 in，in 是比较子串。

class Solution:
def phonePrefix(self, numbers: List[str]) -> bool:
        for i, _ in enumerate(numbers):
                for j in range(len(numbers)):
                        if i != j and numbers[j].startswith(numbers):
                                return False

    return True
   

进阶解法，排序

核心思路：排序 (Sorting)
这道题有一个非常巧妙的性质：对于字符串数组，如果按字典序（字母顺序）进行排序，有前缀关系的字符串一定会紧紧挨在一起！

比如数组 ["00153", "15", "001", "007"]。
排序后变成：["001", "00153", "007", "15"]。
你看，"001" 和它的衍生词 "00153" 紧挨着了！

既然它们紧挨着，我们只需要比较相邻的两个字符串即可，完全不需要两层循环！

class Solution:
        def phonePrefix(self, numbers: List[str]) -> bool:
                # 1. 对字符串数组按字典序排序
                numbers.sort()
    # 2. 只需要对比相邻的元素
    for i in range(len(numbers) - 1):
        # 排序后，如果存在前缀关系，短的必定在前面，长的必定紧随其后
        if numbers[i + 1].startswith(numbers[i]):
            return False
            
    return True

更高阶解法

[i](拓展)：如果是超大规模的数据，或者需要频繁插入查询，这题的标准数据结构是 字典树 (Trie)。但这题数据量小，排序法是最优雅、性价比最高的。

1. 定义字典树的节点类

class TrieNode:
        def init(self):
                self.children = {} # 记录子节点，比如 {'3': TrieNode()}
                self.is_end = False # 标记是否是某个号码的结尾

class Solution:
        def phonePrefix(self, numbers: List[str]) -> bool:
                root = TrieNode()

    # 遍历每一个电话号码
    for num in numbers:
        curr = root
        
        # 将当前号码按字符插入字典树
        for char in num:
            # 如果没有这条路径，就建一个新的节点
            if char not in curr.children:
                curr.children[char] = TrieNode()
            
            curr = curr.children[char]
            
            # 【情况 A】路过了一个已经被标记为结尾的节点
            # 说明之前存过的一个短号码，是当前长号码的前缀
            if curr.is_end:
                return False
        
        # 当前号码插入完毕，停在了最后一个节点
        # 【情况 B】如果这个节点还有孩子，说明当前短号码是之前某个长号码的前缀
        if len(curr.children) > 0:
            return False
            
        # 如果都安全，把当前节点的结尾标记为 True
        curr.is_end = True
        
    return True

LC. 4014. Minimum Total Price After Applying Discounts
Solved
Medium
Hint
You are given two integer arrays prices and discounts.

The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.

You may apply discounts subject to the following rules:

Each discount can be applied to at most one item.
Each item can receive at most one discount.
An item may also receive no discount.
If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.

Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: prices = [10,30,21], discounts = [50,60]

Output: 32.50000

Explanation:

Apply discounts[1] = 60 to prices[1] = 30, thus 30 * (100 - 60) / 100 = 12.
Apply discounts[0] = 50 to prices[2] = 21, thus 21 * (100 - 50) / 100 = 10.5.
prices[0] = 10 receives no discount, so it stays 10.
The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.

Example 2:

Input: prices = [100,70], discounts = [10,40,50]

Output: 92.00000

Explanation:​​​​​​​

Apply discounts[2] = 50 to prices[0] = 100, thus 100 * (100 - 50) / 100 = 50.
Apply discounts[1] = 40 to prices[1] = 70, thus 70 * (100 - 40) / 100 = 42.
The total is 50 + 42 = 92.00000, which is the minimum possible.

Example 3:

Input: prices = [7,3,9], discounts = [100,100]

Output: 3.00000

Explanation:

Apply discounts[0] = 100 to prices[2] = 9, thus 9 * (100 - 100) / 100 = 0.
Apply discounts[1] = 100 to prices[0] = 7, thus 7 * (100 - 100) / 100 = 0.
prices[1] = 3 receives no discount, so it stays 3.
The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.

Constraints:

1 <= prices.length, discounts.length <= 105
1 <= prices[i] <= 105
1 <= discounts[j] <= 100

简单题，直接 Greedy，但是还是要考虑边界条件。

class Solution:
    def minPrice(self, prices: list[int], discounts: list[int]) -> float:
        # greedy
        prices.sort(reverse = True)
        discounts.sort(reverse = True)

        n = min(len(prices), len(discounts))
        ans = 0
   
        for i in range(n):
            ans += (prices[i] * (100 - discounts[i]) * 0.01)

if i < len(prices) - 1:
            for j in range(i+1, len(prices)):
                ans += prices[j]

        return ans

优化后代码

    class Solution:
    def minPrice(self, prices: list[int], discounts: list[int]) -> float:
    # 1. 贪心策略：将价格和折扣都降序排列
    prices.sort(reverse=True)
    discounts.sort(reverse=True)
    n = min(len(prices), len(discounts))
    ans = 0.0

    # 2. 对前 n 个最贵的商品，应用最大的折扣
    for i in range(n):
        # 提示：除以 100.0 比乘 0.01 在某些极端情况下精度更可控
        ans += prices[i] * (100 - discounts[i]) / 100.0

    # 3. 累加剩余没打折的商品
    # 如果 n == len(prices)，range(n, n) 为空，自动不执行，不需要 if 判断
    for j in range(n, len(prices)):
        ans += prices[j]

    return ans

LC 4015. Weighted Sum of a Tree

You are given an integer array parent of length n representing a rooted tree with nodes labeled from 0 to n - 1.

The tree is rooted at node 0, so parent[0] = -1. For each node i where 1 <= i <= n - 1, parent[i] denotes the parent of node i.

You are also given an integer array nums of length n, where nums[i] denotes the value of node i.

The weight of a node i at depth d is nums[i] * (h - d + 1), where h is the height of the tree.

Return the sum of the weights of all nodes in the tree.

The depth of a node is the number of nodes on the path from the root to that node, inclusive, with the root having depth 1.

The height of the tree is the maximum depth among all nodes in the tree.

Example 1:

​​​​​​​

Input: parent = [-1,0,0,0,2,2], nums = [5,2,3,1,4,6]

Output: 37

Explanation:

The height of the tree is 3.

Node nums[i] Depth (d) Weight
0 5 1 5 * (3 - 1 + 1) = 15
1 2 2 2 * (3 - 2 + 1) = 4
2 3 2 3 * (3 - 2 + 1) = 6
3 1 2 1 * (3 - 2 + 1) = 2
4 4 3 4 * (3 - 3 + 1) = 4
5 6 3 6 * (3 - 3 + 1) = 6
The sum of all node weights is 15 + 4 + 6 + 2 + 4 + 6 = 37.

Example 2:

​​​​​​​​​​​​​​

Input: parent = [-1,0,1,2], nums = [1,2,3,4]

Output: 20

Explanation:

The height of the tree is 4.

Node nums[i] Depth (d) Weight
0 1 1 1 * (4 - 1 + 1) = 4
1 2 2 2 * (4 - 2 + 1) = 6
2 3 3 3 * (4 - 3 + 1) = 6
3 4 4 4 * (4 - 4 + 1) = 4
The sum of all node weights is 4 + 6 + 6 + 4 = 20.

Constraints:

1 <= n <= 105
n == parent.length == nums.length
parent[0] == -1
0 <= parent[i] <= n - 1 for all i in [1, n - 1]
1 <= nums[i] <= 106
The input is generated such that the array parent represents a valid tree rooted at node 0.

class Solution:
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
        n = len(parent)
        indexChildDict = defaultdict(list)

        for i in range(n):
            indexChildDict[i] = list()

        for i in range(1, n):
            indexChildDict[parent[i]].append(i)

        depth = 1
        depth_dict = defaultdict(int)

        stack = [0]

        while stack:
            currLayer = len(stack)
            while currLayer:
                curr = stack.pop(0)
                depth_dict[curr] = depth
                if curr in indexChildDict:
                    for index in indexChildDict[curr]:
                        stack.append(index)
                currLayer -= 1
            depth += 1

        ans = 0
        height = depth - 1

        for i in range(n):
            ans += (nums[i] * (height - depth_dict[i] + 1))

        return ans        

不过这个解法问题很大，需要优化

from collections import defaultdict, deque

class Solution:
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
        n = len(parent)
        
        # 1. 建树 (只记录子节点即可)
        children = defaultdict(list)
        for i in range(1, n):
            children[parent[i]].append(i)
            
        # 2. BFS 遍历，记录每个节点的深度
        depths = [0] * n  # 使用数组代替字典，下标即节点号，值是深度
        queue = deque([0])  # 正确的队列初始化
        current_depth = 1
        
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                curr = queue.popleft() # O(1) 出队
                depths[curr] = current_depth
               
                # 直接遍历当前节点的所有子节点
                for child in children[curr]:
                    queue.append(child)
                    
            current_depth += 1
            
        # 此时 current_depth 多加了一次，height 应该是 current_depth - 1
        height = current_depth - 1
        
        # 3. 计算答案
        ans = 0
        for i in range(n):
            ans += nums[i] * (height - depths[i] + 1)
            
        return ans

扩展思考：可以不用 BFS/DFS 吗？
虽然你的 BFS 思路完全没问题，但对于树的父节点数组 parent，其实有一种更进阶的求深度的方法：带记忆化的迭代求解。

因为父节点的值永远指向更上层，我们可以通过向祖先回溯的方式求深度，并通过一个数组记录已经求过的节点，这样连图都不用建，速度非常快：

class Solution:
    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
        n = len(parent)
        depths = [0] * n
        depths[0] = 1
        
        height = 1
        
        # 计算每个节点的深度
        for i in range(1, n):
            # 找当前节点的深度 (向父节点回溯)
            curr = i
            path = []
            while depths[curr] == 0:
                path.append(curr)
                curr = parent[curr]
               
            # 找到了已知深度的祖先，顺藤摸瓜计算沿途节点的深度
            d = depths[curr]
            while path:
                node = path.pop()
                d += 1
                depths[node] = d
               
            height = max(height, depths[i])
            
        # 计算答案
        ans = 0
        for i in range(n):
            ans += nums[i] * (height - depths[i] + 1)
            
        return ans

LC. 3487. Maximum Unique Subarray Sum After Deletion

You are given an integer array nums.

You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that:

All elements in the subarray are unique.
The sum of the elements in the subarray is maximized.
Return the maximum sum of such a subarray.



Example 1:

Input: nums = [1,2,3,4,5]

Output: 15

Explanation:

Select the entire array without deleting any element to obtain the maximum sum.

Example 2:

Input: nums = [1,1,0,1,1]

Output: 1

Explanation:

Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum.

Example 3:

Input: nums = [1,2,-1,-2,1,0,-1]

Output: 3

Explanation:

Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum.



Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

1. class Solution:
   
2.     def maxSum(self, nums: List[int]) -> int:
   
3.         ans = 0
   
4.         numset = set(nums)
   
5.         numlist = sorted(list(numset))
   
6. 
   
7.         if numlist[-1] < 0:
   
8.             return numlist[-1]
   
9.         else:
   
10.             for x in numlist:
    
11.                 if x > 0: ans += x
    
12.             return ans

复制代码

但是我的解法可以优化，就是其实我不需要知道 sorted list，我只需要知道最大值就行，

如果全是负数：因为题目要求至少保留一个元素（不能变为空数组），所以为了让“损失”最小，我们只保留那个最大的负数。

当前的代码：使用了 sorted(list(numset))。虽然题目限制了 N < 100，排序瞬间就能跑完，但在算法面试中，排序的时间复杂度是 O(U log U)（U 是去重后的元素个数）。其实我们并不需要排序，因为我们只是想知道“数组里的最大值是不是小于 0”。优化方向：找最大值只需要 O(N) 的时间。我们可以直接用 Python 内置的 max() 函数，结合集合 set() 和生成器推导式，把代码写得更加优雅和高效。

1. class Solution:
   
2.     def maxSum(self, nums: list[int]) -> int:
   
3.         # 先找出整个数组的最大值
   
4.         max_val = max(nums)
   
5.         
   
6.         # 边界情况：如果最大值都小于 0，说明全是负数。
   
7.         # 为了让和最大且数组不为空，只能选那个最大的负数。
   
8.         if max_val < 0:
   
9.             return max_val
   
10.             
    
11.         # 正常情况：把所有大于 0 的不重复元素加起来
    
12.         unique_nums = set(nums)
    
13.         return sum(x for x in unique_nums if x > 0)

复制代码

LC. 3477. Fruits Into Baskets II
Easy
Topics
conpanies icon
Companies
Hint
You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
Each basket can hold only one type of fruit.
If a fruit type cannot be placed in any basket, it remains unplaced.
Return the number of fruit types that remain unplaced after all possible allocations are made.



Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

fruits[0] = 4 is placed in baskets[1] = 5.
fruits[1] = 2 is placed in baskets[0] = 3.
fruits[2] = 5 cannot be placed in baskets[2] = 4.
Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

fruits[0] = 3 is placed in baskets[0] = 6.
fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
fruits[2] = 1 is placed in baskets[1] = 4.
Since all fruits are successfully placed, we return 0.



Constraints:

n == fruits.length == baskets.length
1 <= n <= 100
1 <= fruits[i], baskets[i] <= 1000


我的解法直接模拟，

1. class Solution:
   
2.     def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
   
3. 
   
4.         ans = 0
   
5. 
   
6.         for f in fruits:
   
7.       
   
8.             for i, b in enumerate(baskets):
   
9.                 if b >= f:
   
10.                     break
    
11.             delIndex = -1
    
12.             if baskets[i] >= f:
    
13.                 delIndex = i
    
14.             else:
    
15.                 ans += 1
    
16.             
    
17.             if delIndex != -1: baskets.pop(i)
    
18.         
    
19.         return ans
    
20. 
    
21. 
    
22.         

复制代码

优化

隐患 1：循环变量 i 的作用域泄漏 (Scope Leakage)
你写了这样一段逻辑：

Python
for i, b in enumerate(baskets):
    if b >= f:
        break
delIndex = -1
if baskets[i] >= f:  # <--- 这里依赖了循环结束后的 i
在 Python 中，如果循环正常结束（没有被 break 打断），i 会保留最后一个元素的索引。虽然在这里因为 baskets 不会为空，代码碰巧能运行，但如果 baskets 为空，i 将完全未定义，直接抛出 UnboundLocalError。这在面试中会被认为是不好的编程习惯。

隐患 2：在遍历时使用 .pop(i) 物理删除元素
在数组中间使用 .pop(i) 去删除元素，底层会把该索引后面的所有元素全部向前移动一位。这会导致该操作本身的时间复杂度变为 O(N)。
虽然本题数据量极小（N <= 100），怎么写都能过，但如果 N 是 10^5，这种写法会直接导致 Time Limit Exceeded (超时)。

🧠 核心思路：原地标记 (In-place Marking)
面对“元素用过就作废”的场景，与其去物理删除它（修改数组长度和索引），不如在原地给它打个标记。

题目说 baskets[i] >= 1，那么我们只要把用过的篮子容量改成 -1 或者 0，它就自然变成了一个“废弃”的篮子，后续再大的水果也放不进去了。这样既保留了原数组的索引，又省去了删除元素的开销。

1. class Solution:
   
2.     def numOfUnplacedFruits(self, fruits: list[int], baskets: list[int]) -> int:
   
3.         unplaced = 0
   
4.         
   
5.         for f in fruits:
   
6.             # 标记当前水果是否成功放入篮子
   
7.             placed = False
   
8.             
   
9.             for i in range(len(baskets)):
   
10.                 if baskets[i] >= f:
    
11.                     baskets[i] = -1  # 核心技巧：原地标记为 -1，代表该篮子已作废
    
12.                     placed = True
    
13.                     break  # 找到了最左边的，直接停止搜索
    
14.                     
    
15.             # 如果遍历完所有篮子都没放进去，未放置数量 +1
    
16.             if not placed:
    
17.                 unplaced += 1
    
18.                
    
19.         return unplaced

复制代码

补充内容 (2026-08-13 10:25 +08:00):
进阶思路：线段树 (了解即可，应对面试追问)我们可以用一棵线段树来维护

1. baskets

复制代码

数组中每个区间的最大值（Max Capacity）。

• 查找最左边满足条件的篮子：
  当拿到一个大小为 $f$ 的水果时，我们从线段树的根节点（代表整个数组）开始往下找：
• • 先看左半边区间的最大值是不是 $\ge f$？如果是，说明左边一定有合格的篮子，毫不犹豫往左子树走（保证了“最左边”的要求）。
  • 如果左半边不够大，再看右半边区间的最大值是不是 $\ge f$？如果是，往右子树走。
  • 如果整个根节点的最大值都 $< f$，说明所有篮子都装不下，直接跳过。
• 更新（原地作废）：
  找到那个具体的篮子（叶子节点）后，把它所在位置的值更新为
  1. -1

  复制代码
  ，并一路往上更新线段树区间最大值。

每一次查找和更新的时间复杂度都是严格的 $O(\log N)$，整体时间复杂度完美降到 $O(N \log N)$，且完美保留了原数组的顺序。

补充内容 (2026-08-13 10:27 +08:00):
太棒了！你有主动去啃高级数据结构的意识，这在面试大厂（尤其是字节、谷歌这类喜欢考 Hard 题的公司）是非常核心的竞争力。
线段树（Segment Tree）听起来吓人，但只要你看透它的本质，它其实就是一个“自带导航功能的二叉树”。
针对“找最左边大于等于 $f$ 的篮子并更新”这个需求，我带你一步步拆解并手写这棵线段树。

🧠 1. 核心思路：线段树是怎么“导航”的？
线段树的每个节点，代表原数组的一个区间。我们让每个节点记录它所代表区间的 最大值 (Max)。
假设

1. baskets = [3, 6, 1, 4]

复制代码

，对应的线段树是这样的：
               [0-3] 最大值:6
              /              \
       [0-1] 最大值:6      [2-3] 最大值:4
       /          \        /          \
[0]值:3      [1]值:6  [2]值:1      [3]值:4

现在来了一个水果，大小为

1. f = 4

复制代码

，我们从树根（代表整个数组）开始找，核心逻辑如下：

• 看整个数组最大值：根节点最大值是
  1. 6

  复制代码
  ，说明这四个篮子里肯定有能装下
  1. 4

  复制代码
  的篮子。进树！
• 永远先看左边（保证最左原则）：

• 左半区
  1. [0-1]

  复制代码
  的最大值是
  1. 6 >= 4

  复制代码
  ，说明左边够用！毫不犹豫往左走（哪怕右边也有能装的，我们也不管，因为题目要求最左边）。
• 到了
  1. [0-1]

  复制代码
  ，再看它的左孩子
  1. [0]

  复制代码
  ，最大值是
  1. 3 < 4

  复制代码
  ，装不下！
• 那只能看它的右孩子
  1. [1]

  复制代码
  ，最大值是
  1. 6 >= 4

  复制代码
  ，找到了！

• 找到了，原地销毁：

• 把
  1. [1]

  复制代码
  的值改成
  1. -1

  复制代码
  （代表用废了）。
• 最关键的一步：顺藤摸瓜往上回溯，重新计算途径节点的最大值。因为
  1. [1]

  复制代码
  废了，
  1. [0-1]

  复制代码
  的最大值就变成了
  1. 3

  复制代码
  ，根节点的最大值就变成了
  1. 4

  复制代码
  （由右半区的
  1. 4

  复制代码
  撑场面）。

你看，一次查找 + 更新，只走了一条从根到叶子的路径，高度是 $\log N$，所以时间复杂度是 $O(\log N)$！

✨ 2. 面试标准代码实现 (Python)
在面试中，写线段树最稳妥、最干净的做法是用一维数组来模拟树（类似堆的写法：左孩子是

1. 2*node+1

复制代码

，右孩子是

1. 2*node+2

复制代码

）。标准需要开辟

1. 4 * N

复制代码

的空间。
class SegmentTree:
    def __init__(self, arr: list[int]):
        self.n = len(arr)
        # 线段树的标准空间是原数组大小的 4 倍
        self.tree = [0] * (4 * self.n)
        # 构建线段树
        self.build(arr, 0, 0, self.n - 1)
        
    def build(self, arr: list[int], node: int, start: int, end: int):
        """递归构建线段树，维护每个区间的最大值"""
        # 如果到了叶子节点（具体某一个篮子）
        if start == end:
            self.tree[node] = arr[start]
            return
            
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # 分别构建左半区和右半区
        self.build(arr, left_child, start, mid)
        self.build(arr, right_child, mid + 1, end)
        
        # 当前节点的最大值 = max(左边最大值, 右边最大值)
        self.tree[node] = max(self.tree[left_child], self.tree[right_child])
        
    def query_and_update(self, node: int, start: int, end: int, f: int) -> int:
        """寻找最左边 >= f 的位置，找到后更新为 -1，返回对应的索引"""
        # 1. 如果当前区间的最大值都比 f 小，说明这片区域全都不行，直接返回 -1
        if self.tree[node] < f:
            return -1
            
        # 2. 如果找到了叶子节点，说明这就是我们要找的那个篮子！
        if start == end:
            self.tree[node] = -1  # 原地作废
            return start
            
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # 3. 核心机制：优先查左边！只要左边的最大值能满足 f，就死死咬住左边往下走
        if self.tree[left_child] >= f:
            res = self.query_and_update(left_child, start, mid, f)
        else:
            # 左边不行，才勉强去右边找
            res = self.query_and_update(right_child, mid + 1, end, f)
            
        # 4. 重点：底下的叶子节点被修改了，所以要向上回溯，更新当前区间的最大值
        self.tree[node] = max(self.tree[left_child], self.tree[right_child])
        
        return res

class Solution:
    def numOfUnplacedFruits(self, fruits: list[int], baskets: list[int]) -> int:
        n = len(fruits)
        # 初始化线段树
        seg_tree = SegmentTree(baskets)
        unplaced = 0
        
        for f in fruits:
            # 在全区间 [0, n-1] 寻找并更新
            # 我们不需要知道具体放到了哪个索引，只需要知道有没有放成功（!= -1）
            res = seg_tree.query_and_update(0, 0, n - 1, f)
            if res == -1:
                unplaced += 1
               
        return unplaced

📊 3. 复杂度分析与面试实战建议

• 时间复杂度：
• 建树：$O(N)$。要把原数组的值放到树的叶子上并向上汇总，遍历整个树的节点。
• 查询并更新：每个水果花费 $O(\log N)$。有 $N$ 个水果，总共 $O(N \log N)$。
• 整体时间：$O(N \log N)$。完美应对 $N = 10^5$ 的数据量！
• 空间复杂度：$O(N)$。
  1. tree

  复制代码
  数组需要 $4N$ 的空间，属于线性空间复杂度。

💡 面试伴侣的小贴士： 在线上面试时，如果遇到类似的题，第一法则永远是先写出 $O(N^2)$ 的暴力解法保证 AC 或拿到基础分（也就是我们上一轮写的代码）。 只有在以下两种情况，你才需要把这套线段树搬出来：

• 题目数据量明确标识了 $N = 10^5$，暴力法绝对会超时。
• 你写完了暴力法，面试官微笑着问：“代码不错，但如果我们想把它优化到 $O(N \log N)$，你有什么思路吗？” 这时你抛出“由于有寻找最左侧限制，普通的排序二分不可行，我们需要维护区间最大值的线段树来定向剪枝”，面试官绝对会眼前一亮！

这个模板你先消化一下，特别是“优先走左孩子”的这个 if 判断，它是解决“最左边”限制的灵魂。有没看懂的地方随时问我！