二分查找（灵神笔记）
模版 红蓝染色法
原始问题：返回有序数组中第一个≥8的数的位置 如果每个数都＜8 返回数组长度
闭区间
def lower_bound(nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
# 循环不变量 nums[left-1]<target nums[right+1]>=target
# 区间左侧外面的都是 < target，区间右侧外面的都是 ≥ target
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
左闭右开区间
def lower_bound(nums: List[int], target: int) -> int:
left = 0
right = len(nums)
while left < right:
# 循环不变量 nums[left-1]<target nums[right]>=target
# 区间左侧外面的都是 < target，区间右侧外面的都是 ≥ target
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # [mid+1,right)
else:
right = mid # [left,mid)
return left # 最后 left right 指向同一个位置 也可以返回 right 区间为空[)
开区间
def lower_bound(nums: List[int], target: int) -> int:
left = -1
right = len(nums)
while left + 1 < right:
# 循环不变量 nums[left]<target nums[right]>=target
mid = (left + right) // 2
if nums[mid] < target:
left = mid # (mid,right)
else:
right = mid # (left,mid)
return right # left + 1
小技巧：
- ＞可以看成 ≥ x 右边的数
- ＜可以看成 ≥ x 左边的数
- ≤ 可以看成＞x
1901 寻找峰值Ⅱ
1901. 寻找峰值 II - 力扣（LeetCode）
一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
示例 1:
输入: mat = [[1,4],[3,2]]
输出: [0,1]
解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。
示例 2:
输入: mat = [[10,20,15],[21,30,14],[7,16,32]]
输出: [1,1]
解释: 30 和 32 都是峰值，所以[1,1]和[2,2]都是可接受的答案。
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 105- 任意两个相邻元素均不相等.
class Solution:
def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
left = -1
right = len(mat) - 1
while left + 1 < right:
i = (left + right) // 2
mx = max(mat[i])
if mx > mat[i + 1][mat[i].index(mx)]:
right = i
else:
left = i
i = right
return [i, mat[i].index(max(mat[i]))]
275 H指数Ⅱ
275. H 指数 II - 力扣（LeetCode）
给你一个整数数组 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.length1 <= n <= 1050 <= citations[i] <= 1000citations按 升序排列
class Solution:
def hIndex(self, citations: List[int]) -> int:
left = 0
right = len(citations) + 1
while left + 1 < right:
mid = (left + right) // 2
# 判断倒数第mid个数是否符合条件 如果符合 后面的数全部符合
# 要求求最大的数 继续试探右边
if (citations[-mid] >= mid):
left = mid # 前面的数染成红色[是]
else:
right = mid # 后面的数染成蓝色[否]
return left
1283 使结果不超过阈值的最小除数
1283. 使结果不超过阈值的最小除数 - 力扣（LeetCode）
给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
题目保证一定有解。
示例 1：
输入：nums = [1,2,5,9], threshold = 6
输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。
示例 2：
输入：nums = [2,3,5,7,11], threshold = 11
输出：3
示例 3：
输入：nums = [19], threshold = 5
输出：4
提示：
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^6nums.length <= threshold <= 10^6
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
//对整个数据范围进行二分 left指向最小值 right指向最大值
int mx = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > mx) {
mx = nums[i];
}
}
int ans = -1;
int left = 0;
int right = mx + 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
int sum = 0;
for (int x : nums) {
sum += (mid + x - 1) / mid;
}
if (sum <= threshold) {
ans = mid;
right = mid;
} else {
left = mid;
}
}
return ans;
}
}
2187 完成旅途的最少时间
2187. 完成旅途的最少时间 - 力扣（LeetCode）
给你一个数组 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 <= 1051 <= time[i], totalTrips <= 107
class Solution {
public long minimumTime(int[] time, int totalTrips) {
Arrays.sort(time);
long left = -1;
//对于[5,10,10] 9 right=45+1
//也就是在[0,45]答案视角进行二分查找
long right = 1L * time[0] * totalTrips + 1;
while(left + 1 < right) {
long mid = left + (right - left) / 2;
long sum = 0;
for (int t : time) {
if (mid < t) {
break;
}
sum += mid / t;
}
if (sum < totalTrips) {
left = mid;
} else {
right = mid;
}
}
return right;
}
}
2226 每个小孩最多能分到多少糖果
2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）
给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。
示例 1：
输入：candies = [5,8,6], k = 3
输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。
示例 2：
输入：candies = [2,5], k = 11
输出：0
解释：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。
提示：
1 <= candies.length <= 1051 <= candies[i] <= 1071 <= k <= 1012
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
if sum(candies) < k:
return 0
left = 0
right = sum(candies) + 1
while left + 1 < right:
mid = (left + right) >> 1
c = 0
for x in candies:
c += x // mid # 求得的kid个数
if c >= k:
left = mid
else:
right = mid
return left
1870 准时到达的列车最小时速
1870. 准时到达的列车最小时速 - 力扣（LeetCode）
给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
- 例如，第
1趟列车需要1.5小时，那你必须再等待0.5小时，搭乘在第 2 小时发车的第2趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。
示例 1：
输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。
示例 2：
输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。
示例 3：
输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。
提示：
n == dist.length1 <= n <= 1051 <= dist[i] <= 1051 <= hour <= 109hours中，小数点后最多存在两位数字
class Solution:
def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
n = len(dist)
hr = round(hour * 100)
if (n - 1) * 100 >= hr:
return -1
def check(speed: int) -> bool:
time = 0
for i in range(n - 1):
time += (dist[i] + speed - 1) // speed
# 通分 化成整数
time *= speed
time += dist[n - 1]
return time * 100 <= hr * speed
l = 0
r = 10 ** 7
while l + 1 < r:
mid = (l + r) // 2
if check(mid):
r = mid
else:
l = mid
return r
1011 在D天内送达包裹的能力
1011. 在 D 天内送达包裹的能力 - 力扣（LeetCode）
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
提示：
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
mx = 0
s = 0
for x in weights:
mx = max(mx, x)
s += x
def check(weights: List[int], t: int, limitDay: int) -> bool:
n = len(weights)
cnt = 0 # 计算运送包裹的天数
i = 1 # 遍历weights的下标
total = weights[0] # 一次运送的重量总和
while i < n:
while i < n and total + weights[i] <= t:
total += weights[i]
i += 1
total = 0
cnt += 1
return cnt <= limitDay
l = mx - 1
r = s
while l + 1 < r:
mid = (l + r) // 2
if check(weights, mid, days):
r = mid
else:
l = mid
return r
875 爱吃香蕉的珂珂
875. 爱吃香蕉的珂珂 - 力扣（LeetCode）
珂珂喜欢吃香蕉。这里有 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 <= 104piles.length <= h <= 1091 <= piles[i] <= 109
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int mx = 0;
for (int x : piles) {
mx = Math.max(mx, x);
}
int left = -1;
int right = mx;
while (left + 1 < right) {
int mid = (left + right) >> 1;
if (check(piles, mid, h)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
public boolean check(int[] p, int k, int h) {
int res = 0;
for (var x : p) {
res += Math.ceil(x * 1.0 / k);
}
return res <= h;
}
}
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
return bisect_left(range(max(piles)), -h, 1, key=lambda k: -sum((p + k - 1) // k for p in piles))
1898 可移除字符的最大数目
1898. 可移除字符的最大数目 - 力扣（LeetCode）
给你两个字符串 s 和 p ，其中 p 是 s 的一个 子序列 。同时，给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组 removable ，该数组是 s 中下标的一个子集（s 的下标也 从 0 开始 计数）。
请你找出一个整数 k（0 <= k <= removable.length），选出 removable 中的 前 k 个下标，然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足：在执行完上述步骤后， p 仍然是 s 的一个 子序列 。更正式的解释是，对于每个 0 <= i < k ，先标记出位于 s[removable[i]] 的字符，接着移除所有标记过的字符，然后检查 p 是否仍然是 s 的一个子序列。
返回你可以找出的 最大 k ，满足在移除字符后 p 仍然是 s 的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。
示例 1：
输入：s = "abcacb", p = "ab", removable = [3,1,0]
输出：2
解释：在移除下标 3 和 1 对应的字符后，"abcacb" 变成 "accb" 。
"ab" 是 "accb" 的一个子序列。
如果移除下标 3、1 和 0 对应的字符后，"abcacb" 变成 "ccb" ，那么 "ab" 就不再是 s 的一个子序列。
因此，最大的 k 是 2 。
示例 2：
输入：s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
输出：1
解释：在移除下标 3 对应的字符后，"abcbddddd" 变成 "abcddddd" 。
"abcd" 是 "abcddddd" 的一个子序列。
示例 3：
输入：s = "abcab", p = "abc", removable = [0,1,2,3,4]
输出：0
解释：如果移除数组 removable 的第一个下标，"abc" 就不再是 s 的一个子序列。
提示：
1 <= p.length <= s.length <= 1050 <= removable.length < s.length0 <= removable[i] < s.lengthp是s的一个 子字符串s和p都由小写英文字母组成removable中的元素 互不相同
class Solution:
def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
ns = len(s)
np = len(p)
n = len(removable)
# 判断是否为子串
def check(k: int) -> bool:
state = [True] * ns
for i in range(k):
state[removable[i]] = False
j = 0
for i in range(ns):
if state[i] and s[i] == p[j]:
j += 1
if j == np:
return True
return False
l = -1
r = n + 1
while l + 1 < r:
mid = (l + r) >> 1
if check(mid):
l = mid
else:
r = mid
return l
1482 制作m束花所需的最少天数
1482. 制作 m 束花所需的最少天数 - 力扣（LeetCode）
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例 1：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3
示例 2：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
示例 3：
输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。
示例 4：
输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束
示例 5：
输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9
提示：
bloomDay.length == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
int n = bloomDay.length;
if (m > n / k) {
return -1;
}
int mx = 0;
for (int d : bloomDay) {
mx = Math.max(mx, d);
}
int left = -1;
int right = mx;
while (left + 1 < right) {
int mid = (left + right) >> 1;
if (check(bloomDay, m, k, mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
public boolean check(int[] bloomDay, int m, int k, int days) {
int fl = 0;
int makefl = 0;
int n = bloomDay.length;
for (int i = 0; i < n; i++) {
if (bloomDay[i] <= days) {
fl++;
if (fl == k) {
makefl++;
fl = 0;
}
} else {
// 要求使用连续的花 只要一个没开就归零
fl = 0;
}
}
return makefl >= m;
}
}
1642 可以到达的最远建筑
1642. 可以到达的最远建筑 - 力扣（LeetCode）
给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
- 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
- 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或
(h[i+1] - h[i])个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
示例 1：
输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。
示例 2：
输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7
示例 3：
输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3
提示：
1 <= heights.length <= 1051 <= heights[i] <= 1060 <= bricks <= 1090 <= ladders <= heights.length
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
int left = -1, right = heights.length;
if (ladders >= right - 1) {
return right - 1;
}
while (left + 1 < right) {
int mid = (left + right) >> 1;
if (check(heights, bricks, ladders, mid)) {
left = mid;
} else {
right = mid;
}
}
return left;
}
public boolean check(int[] heights, int bricks, int ladders, int mid) {
int[] dist = new int[mid];
for (int i = 0; i < mid; i++) {
dist[i] = heights[i + 1] - heights[i];
}
Arrays.sort(dist);
for (int i = mid - 1; i >= 0; i--) {
if (dist[i] < 0) {
break;
}
if (ladders > 0) {
ladders--;
} else if (bricks >= dist[i]) {
bricks -= dist[i];
} else {
return false;
}
}
return true;
}
}
2258 逃离火灾
2258. 逃离火灾 - 力扣（LeetCode）
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0表示草地。1表示着火的格子。2表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
示例 1：
输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出：3
解释：上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。
示例 2：
输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出：-1
解释：上图展示了你马上开始朝安全屋移动的情形。
火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。
所以返回 -1 。
示例 3：
输入：grid = [[0,0,0],[2,2,0],[1,2,0]]
输出：1000000000
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 109 。
提示：
m == grid.lengthn == grid[i].length2 <= m, n <= 3004 <= m * n <= 2 * 104grid[i][j]是0，1或者2。grid[0][0] == grid[m - 1][n - 1] == 0
class Solution:
def maximumMinutes(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# 能否在初始位置停留t分钟，安全到达安全屋
def check(t: int) -> bool:
f = [(i, j) for i, row in enumerate(grid) for j, x in enumerate(row) if x == 1]
on_fire = set(f)
def spread_fire(): # 火bfs
nonlocal f
tmp = f
f = []
for i, j in tmp:
for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in on_fire:
on_fire.add((x, y)) # 标记着火位置
f.append((x, y))
while t and f:
spread_fire()
t -= 1
if (0, 0) in on_fire:
return False # 起点着火
# 人bfs
q = [(0, 0)]
vis = set(q)
while q:
tmp = q
q = []
for i, j in tmp:
if (i, j) in on_fire:
continue # 人遇到火
for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in on_fire and (x, y) not in vis:
if x == m - 1 and y == n - 1:
return True
vis.add((x, y)) # 标记走过的位置
q.append((x, y))
spread_fire()
return False
left = -1
right = m * n + 1
while left + 1 < right:
mid = (left + right) >> 1
if check(mid):
left = mid
else:
right = mid
return left if left < m * n else 10 ** 9
最小化最大值
410 分割数组的最大值
410. 分割数组的最大值 - 力扣（LeetCode）
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], k = 2
输出：9
示例 3：
输入：nums = [1,4,4], k = 3
输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)
class Solution {
public int splitArray(int[] nums, int k) {
int sum = 0;
int mx = 0;
for (int n : nums) {
mx = Math.max(n, mx);
sum += n;
}
int left = mx - 1, right = sum;
while (left + 1 < right) {
int mid = (left + right) >> 1;
if (check(nums, k, mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
public boolean check(int[] nums, int k, int mx) {
int cnt = 1;
int s = 0;
for (int n : nums) {
if (s + n <= mx) {
s += n;
} else {
if (cnt == k) {
return false;
}
cnt++;
s = n;
}
}
return true;
}
}
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
def check(mx: int) -> bool:
cnt = 1
s = 0
for n in nums:
if s + n <= mx:
s += n
else:
if cnt == k:
return False
cnt += 1
s = n
return True
# 左闭右开
left = max(nums)
right = sum(nums)
return left + bisect_left(range(left, right), True, key=check)
2064 分配给商店的最多商品的最小值
2064. 分配给商店的最多商品的最小值 - 力扣（LeetCode）
给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。
你需要将 所有商品 分配到零售商店，并遵守这些规则：
- 一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
- 分配后，每间商店都会被分配一定数目的商品（可能为
0件）。用x表示所有商店中分配商品数目的最大值，你希望x越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。
请你返回最小的可能的 x 。
示例 1：
输入：n = 6, quantities = [11,6]
输出：3
解释： 一种最优方案为：
- 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。
- 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。
分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。
示例 2：
输入：n = 7, quantities = [15,10,10]
输出：5
解释：一种最优方案为：
- 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。
- 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。
- 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。
分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。
示例 3：
输入：n = 1, quantities = [100000]
输出：100000
解释：唯一一种最优方案为：
- 所有 100000 件商品 0 都分配到唯一的商店中。
分配给所有商店的最大商品数目为 max(100000) = 100000 。
提示：
m == quantities.length1 <= m <= n <= 1051 <= quantities[i] <= 105
class Solution:
def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
def check(mid: int) -> bool:
cnt = 0 # 计算所需的商店数量
for q in quantities:
cnt += (q + mid - 1) // mid
return cnt <= n
left, right = 0, max(quantities) + 1
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid
return right
1760 袋子里最少数目的球
1760. 袋子里最少数目的球 - 力扣（LeetCode）
给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次：
- 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。
- 比方说，一个袋子里有
5个球，你可以把它们分到两个新袋子里，分别有1个和4个球，或者分别有2个和3个球。
- 比方说，一个袋子里有
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
示例 1：
输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。
示例 2：
输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。
示例 3：
输入：nums = [7,17], maxOperations = 2
输出：7
提示：
1 <= nums.length <= 1051 <= maxOperations, nums[i] <= 109
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
def check(mid: int) -> bool:
cnt = 0 # 计算操作次数
for n in nums:
cnt += (n + mid - 1) // mid - 1
return cnt <= maxOperations
left, right = 0, max(nums)
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid
return right
2439 最小化数组中的最大值
2439. 最小化数组中的最大值 - 力扣（LeetCode）
给你一个下标从 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.length2 <= n <= 1050 <= nums[i] <= 109
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
def check(mid: int) -> bool:
s = 0
for x in nums:
if x < mid:
s += mid - x
else:
s -= x - mid
if s < 0:
return False
return True
left = 0
right = max(nums)
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid
return right
2560 打家劫舍Ⅳ
2560. 打家劫舍 IV - 力扣（LeetCode）
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
示例 1：
输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。
示例 2：
输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2
class Solution:
def minCapability(self, nums: List[int], k: int) -> int:
def check(mid: int) -> bool:
cnt = 0
i = 0
while i < len(nums):
if nums[i] <= mid:
cnt += 1 # 偷当前房子
i += 1 # 跳过下一个房子
i += 1
return cnt >= k
left, right = 0, max(nums)
while left + 1 < right:
mid = (left + right) >> 1
if check(mid):
right = mid
else:
left = mid
return right
2616 最小化数对的最大差值
2616. 最小化数对的最大差值 - 力扣（LeetCode）
给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
示例 1：
输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。
示例 2：
输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= p <= (nums.length)/2
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
nums.sort()
def check(mid: int) -> bool:
cnt = i = 0
while i < len(nums) - 1:
if nums[i + 1] - nums[i] <= mid:
cnt += 1
i += 2
else:
i += 1
return cnt >= p
left, right = -1, nums[-1] - nums[0]
while left + 1 < right:
mid = (left + right) >> 1
if check(mid):
right = mid
else:
left = mid
return right
2513 最小化两个数组的最大值
2513. 最小化两个数组中的最大值 - 力扣（LeetCode）
给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：
arr1包含uniqueCnt1个 互不相同 的正整数，每个整数都 不能 被divisor1整除 。arr2包含uniqueCnt2个 互不相同 的正整数，每个整数都 不能 被divisor2整除 。arr1和arr2中的元素 互不相同 。
给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。
示例 1：
输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。
arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。
示例 2：
输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
arr1 = [1,2] 和 arr2 = [3] 满足所有条件。
最大值是 3 ，所以返回 3 。
示例 3：
输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
输出：15
解释：
最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。
上述方案是满足所有条件的最优解。
提示：
2 <= divisor1, divisor2 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109
class Solution {
public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
/**
d1 = 4 d2 = 6
arr1 1 2 3 5 6 7 9 10 11 ...
arr2 1 2 3 4 5 7 8 9 10 11 13 14...
arr1 独占6的倍数，但不是4的倍数
arr2 独占4的倍数，但不是6的倍数
arr1 2 既不是4的倍数，又不是6的倍数 = 总个数 - (4的倍数 + 6的倍数 - LCM(4,6)=12的倍数)
最坏情况下
d1 = d2 = 2 只能选奇数
上界为(uniqueCnt1+uniqueCnt2)*2-1
*/
long common = lcm(divisor1, divisor2);
long left = 0, right = ((long) uniqueCnt1 + uniqueCnt2) * 2;
while (left + 1 < right) {
long mid = (left + right) >> 1;
if (check(mid, common, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {
right = mid;
} else {
left = mid;
}
}
return (int) right;
}
public boolean check(long x, long common, int d1, int d2, int u1, int u2) {
long left1 = Math.max(0L, u1 - x / d2 + x / common);
long left2 = Math.max(0L, u2 - x / d1 + x / common);
long and = x - (x / d1 + x / d2 - x / common);
return and >= (left1 + left2);
}
public int gcd(int a, int b) {
while (a != 0) {
int temp = a;
a = b % a;
b = temp;
}
return b;
}
public long lcm(int a, int b) {
return (long) a * b / gcd(a, b);
}
}
class Solution:
def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
lcm = math.lcm(d1, d2)
def check(x: int) -> bool:
left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)
left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)
common = x - (x // d1 + x // d2 - x // lcm)
return common >= left1 + left2
return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key = check)
最大化最小值
1552 两球之间的磁力
1552. 两球之间的磁力 - 力扣（LeetCode）
在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
示例 1：
输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。
示例 2：
输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。
提示：
n == position.length2 <= n <= 10^51 <= position[i] <= 10^9- 所有
position中的整数 互不相同 。 2 <= m <= position.length
class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
def check(x: int, m: int) -> bool:
cnt = 1
pre = position[0]
for i in range(1, len(position)):
if position[i] - pre >= x:
pre = position[i]
cnt += 1
return cnt >= m
position.sort()
left = 0
right = position[-1] - position[0] + 1
while left + 1 < right:
mid = (left + right) // 2
if check(mid, m):
left = mid
else:
right = mid
return left
2861 最大合金数
2861. 最大合金数 - 力扣（LeetCode）
假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 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 <= 1000 <= budget <= 108composition.length == kcomposition[i].length == n1 <= composition[i][j] <= 100stock.length == cost.length == n0 <= stock[i] <= 1081 <= 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:
"""
条件：
1. 创建合金需要 composition[i][j] 份 j 类型金属
2. 你拥有 stock[i] 份 i 类型金属
3. 每购入一份 i 类型金属需要花费 cost[i] 的金钱
4. 预算不超过 budget 金钱
"""
ans = 0
for com in composition:
def check(num: int) -> int:
money = 0
for s, base, c in zip(stock, com, cost):
if base * num > s: # 买额外的金属
money += (base * num - s) * c
if money > budget:
return False
return True
left, right = 0, 10 ** 9 # right = min(stock) + budget
while left + 1 < right:
mid = (left + right) >> 1
if check(mid):
left = mid
else:
right = mid
ans = max(ans, left)
return ans
2517 礼盒的最大甜蜜度
2517. 礼盒的最大甜蜜度 - 力扣（LeetCode）
给你一个正整数数组 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 <= 1051 <= price[i] <= 109
class Solution:
def maximumTastiness(self, price: List[int], k: int) -> int:
price.sort()
def check(mid: int) -> bool:
cnt = 1
pre = price[0]
for p in price:
if p >= pre + mid:
cnt += 1
pre = p
return cnt >= k
left = 0
right = price[-1]
# right = (price[-1] - price[0]) // (k - 1) + 1
while left + 1 < right:
mid = (left + right) >> 1
if check(mid): # 不满足条件 mid增大 left右移
left = mid
else:
right = mid
return left
2528 最大化城市的最小电量
2528. 最大化城市的最小电量 - 力扣（LeetCode）
给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。
每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。
|x|表示x的 绝对值 。比方说，|7 - 5| = 2，|3 - 10| = 7。
一座城市的 电量 是所有能给它供电的供电站数目。
政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。
给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。
这 k 座供电站可以建在多个城市。
示例 1：
输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。
示例 2：
输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。
提示：
n == stations.length1 <= n <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109
class Solution:
def maxPower(self, stations: List[int], r: int, k: int) -> int:
# 在哪里建
# 建在 min(i+r, n-1)
# 影响范围 [i, min(i+2r, n-1)]
n = len(stations)
sum = list(accumulate(stations, initial=0)) # 前缀和
for i in range(n):
stations[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)] # 初始电量
def check(x: int) -> bool:
diff = [0] * n # 差分数组
sum_d = need = 0
for i, power in enumerate(stations):
sum_d += diff[i] # 累加差分值
delta = x - sum_d - power
if delta > 0: # 需要 delta 个供电站
need += delta
if need > k: return False
sum_d += delta
if i + r * 2 + 1 < n:
diff[i + r * 2 + 1] -= delta # 更新差分数组
return True
left = -1
right = sum[n] + k + 1
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
left = mid
else:
right = mid
return left # 左 True 右 False
class Solution {
public long maxPower(int[] stations, int r, int k) {
int n = stations.length;
long[] sum = new long[n + 1];
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + stations[i];
}
long mn = Long.MAX_VALUE;
long[] power = new long[n];
for (int i = 0; i < n; i++) {
power[i] = sum[Math.min(i + r + 1, n)] - sum[Math.max(i - r, 0)];
mn = Math.min(mn, power[i]);
}
long left = mn, right = mn + k + 1;
while (left + 1 < right) {
long mid = left + (right - left) / 2;
if (check(mid, power, n, r, k)) {
left = mid;
} else {
right = mid;
}
}
return left;
}
public boolean check(long x, long[] power, int n, int r, int k) {
long[] diff = new long[n + 1];
long sum_d = 0, need = 0;
for (int i = 0; i < n; i++) {
sum_d += diff[i];
long delta = x - sum_d - power[i];
if (delta > 0) {
need += delta;
if (need > k) return false;
sum_d += delta;
if (i + 2 * r + 1 < n) diff[i + 2 * r + 1] -= delta;
}
}
return true;
}
}
第K小/大
378 有序数组中第K小元素
378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode）
给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于 O(n2) 的解决方案。
示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：
输入：matrix = [[-5]], k = 1
输出：-5
提示：
n == matrix.lengthn == matrix[i].length1 <= n <= 300-109 <= matrix[i][j] <= 109- 题目数据 保证
matrix中的所有行和列都按 非递减顺序 排列 1 <= k <= n2
进阶：
- 你能否用一个恒定的内存(即
O(1)内存复杂度)来解决这个问题? - 你能在
O(n)的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
def check(x: int) -> bool:
cnt = 0 # 二维矩阵 >= mid 的个数
# 从左下角开始查找
i = n - 1
j = 0
while i >= 0 and j < n:
if matrix[i][j] <= mid: # 向右查找
cnt += i + 1
j += 1
else:
i -= 1
return cnt >= k
left, right = matrix[0][0] - 1, matrix[-1][-1]
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid
return right
719 找出第K小的数对距离
719. 找出第 K 小的数对距离 - 力扣（LeetCode）
数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
示例 1：
输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。
示例 2：
输入：nums = [1,1,1], k = 2
输出：0
示例 3：
输入：nums = [1,6,1], k = 3
输出：5
提示：
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
def check(x: int) -> bool:
cnt = 0
i, j = 0, 1
while i < n:
while j < n and nums[j] - nums[i] <= x:
j += 1
cnt += j - i - 1
i += 1
return cnt >= k
left, right = -1, 10 ** 6 # 模糊查找
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid
return right
786 第K个最小的素数分数
786. 第 K 个最小的素数分数 - 力扣（LeetCode）
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
示例 1：
输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5
示例 2：
输入：arr = [1,7], k = 1
输出：[1,7]
提示：
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i]是一个 素数 ，i > 0arr中的所有数字 互不相同 ，且按 严格递增 排序1 <= k <= arr.length * (arr.length - 1) / 2
进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？
class Solution:
def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
n = len(arr)
left, right = 0.0, 1.0
while True:
mid = (left + right) / 2
i, cnt = -1, 0
x, y = 0, 1
for j in range(1, n):
while arr[i + 1] / arr[j] < mid:
i += 1
if arr[i] * y > arr[j] * x:
x, y = arr[i], arr[j]
cnt += i + 1
if cnt == k:
return [x, y]
if cnt > k:
right = mid
else:
left = mid
