2025-2-13-4.5 二分法（基础题）

4.5 二分法（基础题）

作者：灵茶山艾府

链接：https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/

34. 在排序数组中查找元素的第一个和最后一个位置

题目：34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

举例：

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

代码：

def lower_bound(nums: List[int], target: int) -> int:left, right = 0, len(nums)-1while left <= right: # [left,right]mid = (left+right) // 2if nums[mid] < target:left = mid + 1 # [mid+1,right]else:right = mid - 1 # [left,mid-1]return leftclass Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:"""时间复杂度：O(log n)，n为nums的长度空间复杂度：O(1)"""start = lower_bound(nums,target)if start == len(nums) or nums[start] != target:return [-1,-1]end = lower_bound(nums,target+1) - 1return [start,end]

2529. 正整数和负整数的最大计数

题目：2529. 正整数和负整数的最大计数

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

• 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

举例：

示例 1：

输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2：

输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 3：

输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

提示:

• 1 <= nums.length <= 2000
• -2000 <= nums[i] <= 2000
• nums 按 非递减顺序 排列。

代码：

def lower_bound(nums: List[int], target: int) -> int:left, right = 0, len(nums)-1while left <= right:   #[left,right]mid = (left + right) // 2if nums[mid] < target:left = mid + 1 #[mid+1,right]else:right = mid - 1 #[left,mid-1]return left class Solution:def maximumCount(self, nums: List[int]) -> int:# This problem can convert to find the position of the zero"""时间复杂度：O(log n)，n为nums的长度空间复杂度：O(1)"""neg = lower_bound(nums,0) pos = len(nums)-lower_bound(nums,1)return max(neg,pos)

2300. 咒语和药水的成功对数

题目：2300. 咒语和药水的成功对数

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

举例：

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

提示:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 10^5
• 1 <= success <= 10^10

代码：

def lower_bound(nums: List[int], target: int) -> int:left, right = 0, len(nums)-1while left <= right: # [left,right]mid = (left + right)//2if nums[mid] < target:left = mid + 1 # [mid+1,right]else:right = mid - 1 # [left,mid-1]return leftclass Solution:def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:'''python3的数据管理有点神，会根据实际情况提升数据精度时间复杂度：O(mlog n)，m和n分别为spells与potions的长度空间复杂度：O(1)'''potions.sort()ans = []n = len(potions)for s in spells:ans.append(n - lower_bound(potions,success/s))return ans

2563. 统计公平数对的数目

题目：2563. 统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

举例：

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

提示:

• 1 <= nums.length <= 10^5
• nums.length == n
• -10^9 <= nums[i] <= 10^9
• -10^9 <= lower <= upper <= 10^9

代码：

class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:"""# 整出来这个公式就好了nums[i] and nums[j]lower - nums[j] <= nums[i] <= upper - nums[j]且 0 <= i < jdifference between bisect.bisect_left() and bisect_right()(1) 列表中没有查询元素x时，两者返回相同的值，即插入的位置；(2) 只有1个元素x时，left 返回该值所在位置，right 对应位置+1(3) 多个元素x时，left 返回元素x最左面的元素位置 right 最右端元素x的位置+1时间复杂度：O(nlogn)，其中 n 为 nums 的长度。空间复杂度：O(1)。"""nums.sort()ans = 0for j, x  in enumerate(nums):# 查找的元素右边r = bisect_right(nums, upper - x, 0, j) l = bisect_left(nums, lower - x, 0, j) ans += r - lreturn ans 

275. H值数 II（至少问题）

题目：275. H 指数 II

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

举例：

示例 1：

输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。

示例 2：

输入：citations = [1,2,100]
输出：2

提示:

• n == citations.length
• 1 <= n <= 10^5
• 0 <= citations[i] <= 1000
• citations 按 升序排列

代码：

class Solution:def hIndex(self, citations: List[int]) -> int:"""时间复杂度：O(log n)，n为citations的长度空间复杂度：O(1)"""n = len(citations)L,R = 0,n-1while L<=R:mid = (L+R)//2# 至少有n-mid篇的引用数大于citation[mid]if n-mid > citations[mid]:L = mid+1else:R = mid-1return n-L

875. 爱吃香蕉的珂珂（最小问题）

题目：875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

举例：

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23

提示:

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

代码：

class Solution:def minEatingSpeed(self, piles: List[int], h: int) -> int:"""时间复杂度：O(nlog U)，n为piles的长度，U=max（piles）空间复杂度：O(1)"""left, right = 0, max(piles)n = len(piles)if h == n: return rightwhile left+1 < right:mid = (left+right)//2tmp = sum([math.ceil(i/mid) for i in piles])if tmp > h:left = midelse:right = midreturn right

2187. 完成旅途的最少时间(最少，值得多做几遍，好好体会体会！)

题目：2187. 完成旅途的最少时间

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟****旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

举例：

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。

示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

提示:

• 1 <= time.length <= 10^5
• 1 <= time[i], totalTrips <= 10^7

代码：

class Solution:def minimumTime(self, time: List[int], totalTrips: int) -> int:"""时间复杂度：O(nlog U)，n为time的长度，U为二分上下界之差空间复杂度：O(1)"""min_t = min(time)avg = ceil(totalTrips/len(time))left = min_t * avg - 1 # 循环不变量1 sum >= totalTrips 恒为 False# 循环不变量2 sum >= totalTrips 恒为 Trueright = min(max(time)*avg, min_t*totalTrips) # 开区间 (left,right) 不为空while left + 1 < right:mid = (left + right) // 2if sum(mid//t for t in time) >= totalTrips:right = midelse:left = mid# sum(left) < totalTrips 且 sum(right) >= totalTrips return right

2861. 最大合金数（典型应用题）

题目：2861. 最大合金数

假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

所有合金都需要由同一台机器制造。

返回公司可以制造的最大合金数。

举例：

示例 1：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
输出：2
解释：最优的方法是使用第 1 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。
注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。
可以证明在示例条件下最多可以制造 2 份合金。

示例 2：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
输出：5
解释：最优的方法是使用第 2 台机器来制造合金。 
要想制造 5 份合金，我们需要购买： 
- 5 份第 1 类金属。
- 5 份第 2 类金属。 
- 0 份第 3 类金属。 
总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。 
可以证明在示例条件下最多可以制造 5 份合金。

示例 3：

输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
输出：2
解释：最优的方法是使用第 3 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 1 份第 1 类金属。
- 1 份第 2 类金属。
总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。
可以证明在示例条件下最多可以制造 2 份合金。

提示:

• 1 <= n, k <= 100
• 0 <= budget <= 10^8
• composition.length == k
• composition[i].length == n
• 1 <= composition[i][j] <= 100
• stock.length == cost.length == n
• 0 <= stock[i] <= 10^8
• 1 <= cost[i] <= 100

代码：

class Solution:def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:"""跟做应用题似的，真复杂的时间复杂度：O(knlogU)，其中 U=min(stock)+budget。空间复杂度：O(1)。"""ans = 0mx = min(stock) + budgetfor comp in composition:def check(num: int) -> bool:money = 0for s, base, c in zip(stock,comp,cost):if s < base * num:money += (base * num - s) * cif money > budget:return Falsereturn Trueleft, right =  ans, mx+1while left + 1 < right:mid = (left + right) // 2if check(mid):left = midelse:right = midans = leftreturn ans

2439. 最小化数组中的最大值

题目：2439. 最小化数组中的最大值

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

• 选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
• 将 nums[i] 减 1 。
• 将 nums[i - 1] 加 1 。

你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。

举例：

示例 1：

输入：nums = [3,7,1,6]
输出：5
解释：
一串最优操作是：
1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。
2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。
3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。
nums 中最大值为 5 。无法得到比 5 更小的最大值。
所以我们返回 5 。

示例 2：

输入：nums = [10,1]
输出：10
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

提示:

• n == nums.length
• 2 <= n <= 10^5
• 0 <= nums[i] <= 10^9

代码：

class Solution:def minimizeArrayValue(self, nums: List[int]) -> int:"""时间复杂度：O(nlogU)，其中 n 为 nums 的长度，U=max(nums)。空间复杂度：O(1)，仅用到若干变量。"""def check(limit: int) -> bool:extra = 0for i in range(len(nums)-1,0,-1):extra = max(nums[i]+extra-limit,0)return nums[0] + extra <= limitreturn bisect_left(range(max(nums)),True,lo=min(nums),key=check)

2517. 礼盒的最大甜蜜度

题目：2517. 礼盒的最大甜蜜度

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度*。*

举例：

示例 1：

输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

示例 2：

输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。 
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

示例 3：

输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示:

• 2 <= k <= price.length <= 10^5
• 1 <= price[i] <= 10^9

代码：

class Solution:def maximumTastiness(self, price: List[int], k: int) -> int:"""时间复杂度：O(nlogn+nlogU)，其中 n 为 price 的长度，U= (max(price)−min(price))/(k−1)空间复杂度：O(1)。"""def check(d: int) -> int:cnt = 1pre = price[0] # 先选甜度最小的for p in price:if p >= pre + d:cnt += 1pre = p  # 上一个选的甜度return cntprice.sort()left = 0right = (price[-1]-price[0]) // (k - 1) + 1while left + 1 < right:mid = (left + right) // 2if check(mid) >= k:left = midelse:right = midreturn left