LeetCode Go · 二分查找（4）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

1760. 袋子里最少数目的球

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个整数数组 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 <= 105
• 1 <= maxOperations, nums[i] <= 109

方法一：二分查找 · Go 实现

思考

一次操作把一袋拆成两袋正整数，目标是最小化最终各袋的最大值，操作次数不超过 $\mathit{\text{maxOperations}}$。最大值越大越容易满足，具有单调性。

二分上限 $mx$：一袋 $x$ 需拆 $(x-1)//mx$ 次。若总次数不超过限制则尝试更小的 $mx$。答案为最小可行上限。

本题需要我们最小化开销，即最小化单个袋子里球数目的最大值。随着最大值的增大，操作次数会减少，越容易满足条件。

因此，我们可以二分枚举单个袋子里球数目的最大值，判断是否能在 $\mathit{\text{maxOperations}}$ 次操作内得到。

具体地，我们定义二分查找的左边界 $l=1$，右边界 $r=max(\mathit{\text{nums}})$。然后我们不断二分枚举中间值 $\mathit{\text{mid}}=\frac{l+r}{2}$，对于每个 $\mathit{\text{mid}}$，我们计算在这个 $\mathit{\text{mid}}$ 下，需要的操作次数。如果操作次数小于等于 $\mathit{\text{maxOperations}}$，说明 $\mathit{\text{mid}}$ 满足条件，我们将右边界 $r$ 更新为 $\mathit{\text{mid}}$，否则将左边界 $l$ 更新为 $\mathit{\text{mid}}+1$。

最后，我们返回左边界 $l$ 即可。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别是数组 $\mathit{\text{nums}}$ 的长度和最大值。空间复杂度 $O(1)$。

func minimumSize(nums []int, maxOperations int) int {
	r := slices.Max(nums)
	return 1 + sort.Search(r, func(mx int) bool {
		mx++
		s := 0
		for _, x := range nums {
			s += (x - 1) / mx
		}
		return s <= maxOperations
	})
}

力扣原题 · Doocs 题解来源

1793. 好子数组的最大分数

困难1 种解法

标签：栈、数组、双指针、二分查找、单调栈

题目、示例与约束

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

 

示例 1：

输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

示例 2：

输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 2 * 104
• 0 <= k < nums.length

方法一：单调栈 · Go 实现

思考

好子数组必须覆盖下标 $k$，分数为长度乘区间最小值。 $n\le {10}^5$，不能枚举所有覆盖 $k$ 的区间。

改以每个位置作为最小值：单调栈求出左右第一个更小元，得到它能控制的最大区间；若该区间仍覆盖 $k$，则用 $v\times \mathit{\text{width}}$ 更新答案。

我们可以枚举 $nums$ 中的每个元素 $nums[i]$ 作为子数组的最小值，利用单调栈找出其左边第一个小于 $nums[i]$ 的位置 $left[i]$ 和右边第一个小于等于 $nums[i]$ 的位置 $right[i]$，则以 $nums[i]$ 为最小值的子数组的分数为 $nums[i]\times (right[i]-left[i]-1)$。

需要注意的是，只有当左右边界 $left[i]$ 和 $right[i]$ 满足 $left[i]+1\le k\le right[i]-1$ 时，答案才有可能更新。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

func maximumScore(nums []int, k int) (ans int) {
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = -1
		right[i] = n
	}
	stk := []int{}
	for i, v := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		v := nums[i]
		for len(stk) > 0 && nums[stk[len(stk)-1]] > v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	for i, v := range nums {
		if left[i]+1 <= k && k <= right[i]-1 {
			ans = max(ans, v*(right[i]-left[i]-1))
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1818. 绝对差值和

中等1 种解法

标签：数组、二分查找、有序集合、排序

题目、示例与约束

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。

数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。

你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。

在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。

|x| 定义为：

• 如果 x >= 0 ，值为 x ，或者
• 如果 x <= 0 ，值为 -x

 

示例 1：

输入：nums1 = [1,7,5], nums2 = [2,3,5]
输出：3
解释：有两种可能的最优方案：
- 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
- 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3

示例 2：

输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
输出：0
解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0

示例 3：

输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
输出：20
解释：将第一个元素替换为第二个元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

 

提示：

• n == nums1.length
• n == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 105

方法一：排序 + 二分查找 · Go 实现

思考

至多替换 $nums1$ 中一个位置，使 $\sum |nums1[i]-nums2[i]|$ 最小。若对每个位置枚举所有可替换值，时间为 $O(n^2)$。 $n\le {10}^5$，无法通过。

先算出不替换时的总和 $s$。替换 $i$ 的收益是 $|nums1[i]-nums2[i]|$ 与「 $nums1$ 中最接近 $nums2[i]$ 的值」之差的差。把 $nums1$ 排序后对每个 $nums2[i]$ 二分相邻候选，记录最大收益 $mx$，答案为 $s-mx$。

根据题意，我们可以先计算出在不进行替换的情况下，nums1 和 nums2 的绝对差值和，记为 $s$。

接下来，我们枚举 nums1 中的每个元素 $nums1[i]$，将其替换为与 $nums2[i]$ 最接近的元素，并且这个最接近的元素在 nums1 中。因此，我们可以在枚举之前，先复制一份 nums1，得到数组 nums，并将 nums 排序。接下来，就在 nums 中二分查找与 $nums2[i]$ 最接近的元素，记为 $nums[j]$，并计算 $|nums1[i]-nums2[i]|-|nums[j]-nums2[i]|$，更新差值 $mx$ 的最大值。

最后，我们将 $s$ 减去 $mx$，即为答案。注意取模操作。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 nums1 的长度。

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
	n := len(nums1)
	nums := make([]int, n)
	copy(nums, nums1)
	sort.Ints(nums)
	s, mx := 0, 0
	const mod int = 1e9 + 7
	for i, a := range nums1 {
		b := nums2[i]
		s = (s + abs(a-b)) % mod
	}
	for i, a := range nums1 {
		b := nums2[i]
		d1, d2 := abs(a-b), 1<<30
		j := sort.SearchInts(nums, b)
		if j < n {
			d2 = min(d2, abs(nums[j]-b))
		}
		if j > 0 {
			d2 = min(d2, abs(nums[j-1]-b))
		}
		mx = max(mx, d1-d2)
	}
	return (s - mx + mod) % mod
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

1847. 最近的房间

困难1 种解法

标签：数组、二分查找、有序集合、排序

题目、示例与约束

一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。

同时给你 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferredj, minSizej] 。第 j 个查询的答案是满足如下条件的房间 id ：

• 房间的面积 至少 为 minSizej ，且
• abs(id - preferredj) 的值 最小 ，其中 abs(x) 是 x 的绝对值。

如果差的绝对值有 相等 的，选择 最小 的 id 。如果 没有满足条件的房间 ，答案为 -1 。

请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。

 

示例 1：

输入：rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
输出：[3,-1,3]
解释：查询的答案如下：
查询 [3,1] ：房间 3 的面积为 2 ，大于等于 1 ，且号码是最接近 3 的，为 abs(3 - 3) = 0 ，所以答案为 3 。
查询 [3,3] ：没有房间的面积至少为 3 ，所以答案为 -1 。
查询 [5,2] ：房间 3 的面积为 2 ，大于等于 2 ，且号码是最接近 5 的，为 abs(3 - 5) = 2 ，所以答案为 3 。

示例 2：

输入：rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
输出：[2,1,3]
解释：查询的答案如下：
查询 [2,3] ：房间 2 的面积为 3 ，大于等于 3 ，且号码是最接近的，为 abs(2 - 2) = 0 ，所以答案为 2 。
查询 [2,4] ：房间 1 和 3 的面积都至少为 4 ，答案为 1 因为它房间编号更小。
查询 [2,5] ：房间 3 是唯一面积大于等于 5 的，所以答案为 3 。

 

提示：

• n == rooms.length
• 1 <= n <= 105
• k == queries.length
• 1 <= k <= 104
• 1 <= roomIdi, preferredj <= 107
• 1 <= sizei, minSizej <= 107

方法一：离线查询 + 有序集合 + 二分查找 · Go 实现

思考

每个询问要在面积不小于 $\mathit{\text{minSize}}$ 的房间中找与 $\mathit{\text{preferred}}$ 编号最接近者。若对每个询问扫描全部房间， $n,k\le {10}^5$ 无法通过。

询问互不影响，可按 $\mathit{\text{minSize}}$ 升序离线处理。房间同样按面积排序后，用有序集合维护「当前仍满足面积」的编号，面积不够的房间不断删去。在有序编号上二分 $\mathit{\text{preferred}}$ 的左右邻居即可。

我们注意到，查询的顺序并不影响答案，而且题目中涉及到房间面积的大小关系，因此，我们可以将查询按照最小面积从小到大排序，这样我们就可以从小到大依次处理每个查询。另外，我们也将房间按照面积从小到大排序。

接下来，我们创建一个有序列表，将所有房间的编号加入有序列表中。

然后，我们从小到大依次处理每个查询。对于每个查询，我们首先将所有面积小于等于当前查询的最小面积的房间从有序列表中移除。然后，我们在剩余的房间中，使用二分查找找到最接近当前查询的房间编号。如果不存在这样的房间，那么我们就返回 $-1$。

时间复杂度 $O(n\times \log n+k\times \log k)$，空间复杂度 $O(n+k)$。其中 $n$ 和 $k$ 分别是房间数和查询数。

func closestRoom(rooms [][]int, queries [][]int) []int {
	n, k := len(rooms), len(queries)
	sort.Slice(rooms, func(i, j int) bool { return rooms[i][1] < rooms[j][1] })
	idx := make([]int, k)
	ans := make([]int, k)
	for i := range idx {
		idx[i] = i
		ans[i] = -1
	}
	sort.Slice(idx, func(i, j int) bool { return queries[idx[i]][1] < queries[idx[j]][1] })
	rbt := redblacktree.NewWithIntComparator()
	merge := func(rbt *redblacktree.Tree, key, value int) {
		if v, ok := rbt.Get(key); ok {
			nxt := v.(int) + value
			if nxt == 0 {
				rbt.Remove(key)
			} else {
				rbt.Put(key, nxt)
			}
		} else {
			rbt.Put(key, value)
		}
	}
	for _, room := range rooms {
		merge(rbt, room[0], 1)
	}
	i := 0

	for _, j := range idx {
		prefer, minSize := queries[j][0], queries[j][1]
		for i < n && rooms[i][1] < minSize {
			merge(rbt, rooms[i][0], -1)
			i++
		}
		if i == n {
			break
		}
		c, _ := rbt.Ceiling(prefer)
		f, _ := rbt.Floor(prefer)
		if c != nil {
			ans[j] = c.Key.(int)
		}
		if f != nil && (ans[j] == -1 || ans[j]-prefer >= prefer-f.Key.(int)) {
			ans[j] = f.Key.(int)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1851. 包含每个查询的最小区间

困难1 种解法

标签：数组、二分查找、排序、扫描线、堆（优先队列）

题目、示例与约束

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。

再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

以数组形式返回对应查询的所有答案。

 

示例 1：

输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：
- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。

示例 2：

输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：
- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
- Query = 19：不存在包含 19 的区间，答案为 -1 。
- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。

 

提示：

• 1 <= intervals.length <= 105
• 1 <= queries.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 107
• 1 <= queries[j] <= 107

方法一：排序 + 离线查询 + 优先队列（小根堆） · Go 实现

思考

每个询问求覆盖该点的最短区间长度。区间与询问均达 ${10}^5$，对每个点扫描全部区间不可行。

询问离线按坐标排序，区间按左端排序。用小根堆保存「已加入且可能覆盖当前询问」的 $(\mathit{\text{长度}},\mathit{\text{右端}})$：左端已越过询问的区间入堆，右端已不够的弹出。堆顶即为当前点的最短覆盖。

我们注意到，题目中查询的顺序并不会影响答案，并且涉及到的区间也不会发生变化，因此，我们考虑将所有的查询按照从小到大的顺序进行排序，同时将所有的区间按照左端点从小到大的顺序进行排序。

我们使用一个优先队列（小根堆） $pq$ 来维护当前所有的区间，队列的每个元素是一个二元组 $(v,r)$，表示一个区间长度为 $v$，右端点为 $r$ 的区间。初始时，优先队列为空。另外，我们定义一个指针 $i$，指向当前遍历到的区间，初始时 $i=0$。

我们按照从小到大的顺序依次遍历每个查询 $(x,j)$，并进行如下操作：

• 如果指针 $i$ 尚未遍历完所有的区间，并且当前遍历到的区间 $[a,b]$ 的左端点小于等于 $x$，那么我们将该区间加入优先队列中，并将指针 $i$ 后移一位，循环此过程；
• 如果优先队列不为空，并且堆顶元素的右端点小于 $x$，那么我们将堆顶元素弹出，循环此过程；
• 此时，如果优先队列不为空，那么堆顶元素就是包含 $x$ 的最小区间。我们将其长度 $v$ 加入答案数组 $ans$ 中。

在上述过程结束后，我们返回答案数组 $ans$ 即可。

时间复杂度 $O(n\times \log n+m\times \log m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别是数组 $intervals$ 和 $queries$ 的长度。

func minInterval(intervals [][]int, queries []int) []int {
	n, m := len(intervals), len(queries)
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	qs := make([][2]int, m)
	ans := make([]int, m)
	for i := range qs {
		qs[i] = [2]int{queries[i], i}
		ans[i] = -1
	}
	sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
	pq := hp{}
	i := 0
	for _, q := range qs {
		x, j := q[0], q[1]
		for i < n && intervals[i][0] <= x {
			a, b := intervals[i][0], intervals[i][1]
			heap.Push(&pq, pair{b - a + 1, b})
			i++
		}
		for len(pq) > 0 && pq[0].r < x {
			heap.Pop(&pq)
		}
		if len(pq) > 0 {
			ans[j] = pq[0].v
		}
	}
	return ans
}

type pair struct{ v, r int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

力扣原题 · Doocs 题解来源

1855. 下标对中的最大距离

中等2 种解法

标签：数组、双指针、二分查找

题目、示例与约束

给你两个 非递增 的整数数组 nums1​​​​​​ 和 nums2​​​​​​ ，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i​​ 。​​

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

 

示例 1：

输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

 

提示：

• 1 <= nums1.length <= 105
• 1 <= nums2.length <= 105
• 1 <= nums1[i], nums2[j] <= 105
• nums1 和 nums2 都是 非递增 数组

方法一：二分查找 · Go 实现

思考

两数组均非递增，求满足 $i\le j$ 且 $nums1[i]\le nums2[j]$ 的最大 $j-i$。枚举全部下标对为 $O(mn)$， $n\le {10}^5$ 不可行。

对固定 $i$，最远的合法 $j$ 是 $nums2[i:]$ 中最后一个不小于 $nums1[i]$ 的位置。将 $nums2$ 反转后可用二分查找该位置。

假设 $nums1$, $nums2$ 的长度分别为 $m$ 和 $n$。

遍历数组 $nums1$，对于每个数字 $nums1[i]$，二分查找 $nums2$ 在 $[i,n)$ 范围内的数字，找到最后一个大于等于 $nums1[i]$ 的位置 $j$，计算此位置与 $i$ 的距离，并更新最大距离值 $ans$。

时间复杂度 $O(m\times \log n)$，其中 $m$ 和 $n$ 分别为 $nums1$ 和 $nums2$ 的长度。空间复杂度 $O(1)$。

func maxDistance(nums1 []int, nums2 []int) int {
	ans, n := 0, len(nums2)
	for i, num := range nums1 {
		left, right := i, n-1
		for left < right {
			mid := (left + right + 1) >> 1
			if nums2[mid] >= num {
				left = mid
			} else {
				right = mid - 1
			}
		}
		if ans < left-i {
			ans = left - i
		}
	}
	return ans
}

方法二：双指针 · Go 实现

思考

方法一只用了 $nums2$ 的单调性。 $nums1$ 同样非递增，故 $i$ 增大时对应的最远 $j$ 不会回退。双指针同步右移，总时间降为线性。

在方法一中，我们只利用到 $nums2$ 是非递增数组这一条件，实际上， $nums1$ 也是非递增数组，我们可以用双指针 $i$ 和 $j$ 来遍历 $nums1$ 和 $nums2$。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别为 $nums1$ 和 $nums2$ 的长度。空间复杂度 $O(1)$。

func maxDistance(nums1 []int, nums2 []int) int {
	m, n := len(nums1), len(nums2)
	ans := 0
	for i, j := 0, 0; i < m; i++ {
		for j < n && nums1[i] <= nums2[j] {
			j++
		}
		if ans < j-i-1 {
			ans = j - i - 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1862. 向下取整数对和

困难1 种解法

标签：数组、数学、二分查找、计数、枚举、前缀和

题目、示例与约束

给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对109 + 7 取余 的结果。

函数 floor() 返回输入数字的整数部分。

 

示例 1：

输入：nums = [2,5,9]
输出：10
解释：
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我们计算每一个数对商向下取整的结果并求和得到 10 。

示例 2：

输入：nums = [7,7,7,7,7,7,7]
输出：49

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

方法一：值域前缀和 + 优化枚举 · Go 实现

思考

求 $\sum _{i,j}\lfloor nums[i]/nums[j]\rfloor$。枚举数对为 $O(n^2)$， $n\le {10}^5$ 不可行。

值域不超过 ${10}^5$，先对值做频次前缀和。枚举分母 $y$ 与商 $d$，落在 $[dy,dy+y)$ 的分子个数可由前缀和一次取出，再乘 $cnt[y]\cdot d$。调和级数枚举总复杂度 $O(M\log M)$。

我们先统计数组 $nums$ 中每个元素出现的次数，记录在数组 $cnt$ 中，然后计算数组 $cnt$ 的前缀和，记录在数组 $s$ 中，即 $s[i]$ 表示小于等于 $i$ 的元素的个数。

接下来，我们枚举分母 $y$ 以及商 $d$，利用前缀和数组计算得到分子的个数 $s[min(mx,d\times y+y-1)]-s[d\times y-1]$，其中 $mx$ 表示数组 $nums$ 中的最大值。那么，我们将分子的个数，乘以分母的个数 $cnt[y]$，再乘以商 $d$，就可以得到所有满足条件的分式的值，将这些值累加起来，就可以得到答案。

时间复杂度 $O(M\times \log M)$，空间复杂度 $O(M)$，其中 $M$ 表示数组 $nums$ 中的最大值。

func sumOfFlooredPairs(nums []int) (ans int) {
	mx := slices.Max(nums)
	cnt := make([]int, mx+1)
	s := make([]int, mx+1)
	for _, x := range nums {
		cnt[x]++
	}
	for i := 1; i <= mx; i++ {
		s[i] = s[i-1] + cnt[i]
	}
	const mod int = 1e9 + 7
	for y := 1; y <= mx; y++ {
		if cnt[y] > 0 {
			for d := 1; d*y <= mx; d++ {
				ans += d * cnt[y] * (s[min((d+1)*y-1, mx)] - s[d*y-1])
				ans %= mod
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1870. 准时到达的列车最小时速

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个浮点数 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.length
• 1 <= n <= 105
• 1 <= dist[i] <= 105
• 1 <= hour <= 109
• hours 中，小数点后最多存在两位数字

方法一：二分查找 · Go 实现

思考

除最后一趟外每段时间向上取整，求能在 $hour$ 内到达的最小整数速度。速度越大用时越短，具有单调性。列车数大于 $\lceil hour\rceil$ 时即使每段只花 $1$ 小时也不够。

对速度在 $[1,{10}^7]$ 上二分：按段累加 $d/v$（中间段向上取整）判断是否不超过 $hour$。找不到则返回 $-1$。

我们注意到，如果一个速度值 $v$ 能够使得我们在规定时间内到达，那么对于任意 $v^{\prime }>v$，我们也一定能在规定时间内到达。这存在着单调性，因此我们可以使用二分查找，找到最小的满足条件的速度值。

在二分查找之前，我们需要先判断是否有可能在规定时间内到达。如果列车数量大于向上取整的规定时间，那么一定无法在规定时间内到达，直接返回 $-1$。

接下来，我们定义二分的左右边界为 $l=1$, $r={10}^7+1$，然后我们每次取中间值 $\mathit{\text{mid}}=\frac{l+r}{2}$，判断是否满足条件。如果满足条件，我们将右边界移动到 $\mathit{\text{mid}}$，否则将左边界移动到 $\mathit{\text{mid}}+1$。

问题转化为判断一个速度值 $v$ 是否能够在规定时间内到达。我们可以遍历每一趟列车，计算每一趟列车的运行时间 $t=\frac{d}{v}$，如果是最后一趟列车，我们直接加上 $t$，否则我们向上取整加上 $t$。最后判断总时间是否小于等于规定时间，如果是则说明满足条件。

二分结束后，如果左边界超过了 ${10}^7$，说明无法在规定时间内到达，返回 $-1$，否则返回左边界。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别为列车数量和速度的上界。空间复杂度 $O(1)$。

func minSpeedOnTime(dist []int, hour float64) int {
	if float64(len(dist)) > math.Ceil(hour) {
		return -1
	}
	const m int = 1e7
	n := len(dist)
	ans := sort.Search(m+1, func(v int) bool {
		v++
		s := 0.0
		for i, d := range dist {
			t := float64(d) / float64(v)
			if i == n-1 {
				s += t
			} else {
				s += math.Ceil(t)
			}
		}
		return s <= hour
	}) + 1
	if ans > m {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1885. 统计数对 🔒

中等1 种解法

标签：数组、双指针、二分查找、排序

题目、示例与约束

给你两个长度为 n 的整数数组 nums1 和 nums2 ，找出所有满足 i < j 且 nums1[i] + nums1[j] > nums2[i] + nums2[j] 的数对 (i, j) 。

返回满足条件数对的 个数 。

 

示例 1：

输入：nums1 = [2,1,2,1], nums2 = [1,2,1,2]
输出：1
解释：满足条件的数对有 1 个：(0, 2) ，因为 nums1[0] + nums1[2] = 2 + 2 > nums2[0] + nums2[2] = 1 + 1

示例 2：

输入：nums1 = [1,10,6,2], nums2 = [1,4,1,5]
输出：5
解释：以下数对满足条件：
- (0, 1) 因为 nums1[0] + nums1[1] = 1 + 10 > nums2[0] + nums2[1] = 1 + 4
- (0, 2) 因为 nums1[0] + nums1[2] = 1 + 6 > nums2[0] + nums2[2] = 1 + 1
- (1, 2) 因为 nums1[1] + nums1[2] = 10 + 6 > nums2[1] + nums2[2] = 4 + 1
- (1, 3) 因为 nums1[1] + nums1[3] = 10 + 2 > nums2[1] + nums2[3] = 4 + 5
- (2, 3) 因为 nums1[2] + nums1[3] = 6 + 2 > nums2[2] + nums2[3] = 1 + 5

 

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 105

方法一：排序 + 双指针 · Go 实现

思考

统计 $i<j$ 且 $nums1[i]+nums1[j]>nums2[i]+nums2[j]$ 的对数。移项后即 $a[i]+a[j]>0$，其中 $a=nums1-nums2$。双层枚举为 $O(n^2)$， $n\le {10}^5$ 不可行。

对 $a$ 排序后，右指针从大到小：左指针推进到 $a[l]+a[r]>0$，则 $[l,r)$ 均可与 $r$ 配对。每个指针只走一遍。

我们可以将题目的不等式转化为 $\mathit{\text{nums1}}[i]-\mathit{\text{nums2}}[i]+\mathit{\text{nums1}}[j]-\mathit{\text{nums2}}[j]>0$，即 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j]>0$，其中 $\mathit{\text{nums}}[i]=\mathit{\text{nums1}}[i]-\mathit{\text{nums2}}[i]$。

即对于数组 $\mathit{\text{nums}}$，我们要找到所有满足 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[j]>0$ 的数对 $(i,j)$。

我们不妨对数组 $\mathit{\text{nums}}$ 进行排序，然后使用双指针的方法，初始化左指针 $l=0$，右指针 $r=n-1$。每一次，我们判断 $\mathit{\text{nums}}[l]+\mathit{\text{nums}}[r]$ 是否小于等于 $0$，如果是，我们循环将左指针右移，直到 $\mathit{\text{nums}}[l]+\mathit{\text{nums}}[r]>0$，此时，以 $l$, $l+1$, $l+2$, $\cdots$, $r-1$ 为左指针，且 $r$ 为右指针的所有数对都满足条件，共有 $r-l$ 个数对，我们将其加入答案中。然后将右指针左移，继续进行上述操作，直到 $l\ge r$。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

func countPairs(nums1 []int, nums2 []int) (ans int64) {
	n := len(nums1)
	nums := make([]int, n)
	for i, x := range nums1 {
		nums[i] = x - nums2[i]
	}
	sort.Ints(nums)
	l, r := 0, n-1
	for l < r {
		for l < r && nums[l]+nums[r] <= 0 {
			l++
		}
		ans += int64(r - l)
		r--
	}
	return
}

力扣原题 · Doocs 题解来源

1889. 装包裹的最小浪费空间

困难1 种解法

标签：数组、二分查找、前缀和、排序

题目、示例与约束

给你 n 个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。总共有 m 个供应商提供 不同尺寸 的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 小于等于 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。

包裹的尺寸用一个整数数组 packages 表示，其中 packages[i] 是第 i 个包裹的尺寸。供应商用二维数组 boxes 表示，其中 boxes[j] 是第 j 个供应商提供的所有箱子尺寸的数组。

你想要选择 一个供应商 并只使用该供应商提供的箱子，使得 总浪费空间最小 。对于每个装了包裹的箱子，我们定义 浪费的 空间等于 箱子的尺寸 - 包裹的尺寸 。总浪费空间 为 所有 箱子中浪费空间的总和。

• 比方说，如果你想要用尺寸数组为 [4,8] 的箱子装下尺寸为 [2,3,5] 的包裹，你可以将尺寸为 2 和 3 的两个包裹装入两个尺寸为 4 的箱子中，同时把尺寸为 5 的包裹装入尺寸为 8 的箱子中。总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

请你选择 最优 箱子供应商，使得 总浪费空间最小 。如果 无法 将所有包裹放入箱子中，请你返回 -1 。由于答案可能会 很大 ，请返回它对 109 + 7 取余 的结果。

 

示例 1：

输入：packages = [2,3,5], boxes = [[4,8],[2,8]]
输出：6
解释：选择第一个供应商最优，用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。
总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

示例 2：

输入：packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
输出：-1
解释：没有箱子能装下尺寸为 5 的包裹。

示例 3：

输入：packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
输出：9
解释：选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。
总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。

 

提示：

• n == packages.length
• m == boxes.length
• 1 <= n <= 105
• 1 <= m <= 105
• 1 <= packages[i] <= 105
• 1 <= boxes[j].length <= 105
• 1 <= boxes[j][k] <= 105
• sum(boxes[j].length) <= 105
• boxes[j] 中的元素 互不相同 。

方法一：排序 + 二分查找 · Go 实现

思考

每个供应商提供一组箱子，箱子只能装不大于其尺寸的包裹且每个箱子至多一个包裹，求最小浪费空间。包裹与箱子都可达 ${10}^5$，对每个箱子扫描包裹不可行。

包裹排序后，对每个供应商的箱子也排序。用二分把能装进当前箱子、尚未装箱的包裹一次性切出，累加 $b\times$ 个数。总空间减包裹总和即浪费，取各供应商的最小者。

我们首先对包裹的尺寸数组 $packages$ 进行排序。

然后遍历每个供应商的箱子数组 $boxes$，对于每个箱子数组 $boxes$，我们也对其进行排序。

如果当前箱子数组中最大的箱子尺寸小于包裹数组中最大的包裹尺寸，那么我们就可以跳过这个供应商，因为这个供应商的箱子无法装下最大的包裹。否则，我们从小到大遍历当前供应商的每个箱子 $b$，用一个指针 $i$ 指向当前待装箱的包裹。

接下来，我们在数组 $packages$ 中二分查找，找到第一个尺寸大于 $b$ 的包裹 $packages[j]$。那么我们可以用箱子 $b$ 装下 $packages[i..j-1]$ 中的所有包裹，此时总空间为 $b\times (j-i)$。然后我们将指针 $i$ 移动到 $j$，继续寻找下一个箱子的装包情况。

遍历完该供应商的所有箱子后，我们就可以得到该供应商所需的箱子总空间。我们遍历所有供应商，找到所需箱子的最小总空间，那么浪费的空间就是总空间减去所有包裹的总尺寸。

时间复杂度 $O(n\times \log n+l\times \log l+l\times \log n)$，空间复杂度 $O(\log n+\log l)$。其中 $n$ 是包裹的数量，而 $l$ 是所有箱子的数量。

func minWastedSpace(packages []int, boxes [][]int) int {
	n := len(packages)
	inf := 1 << 62
	sort.Ints(packages)
	ans := inf
	for _, box := range boxes {
		sort.Ints(box)
		if packages[n-1] > box[len(box)-1] {
			continue
		}
		s, i := 0, 0
		for _, b := range box {
			j := sort.SearchInts(packages[i:], b+1) + i
			s += (j - i) * b
			i = j
		}
		ans = min(ans, s)
	}
	if ans == inf {
		return -1
	}
	s := 0
	for _, p := range packages {
		s += p
	}
	const mod = 1e9 + 7
	return (ans - s) % mod
}

力扣原题 · Doocs 题解来源

1891. 割绳子 🔒

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给定一个整数数组 ribbons 和一个整数 k，数组每项 ribbons[i] 表示第 i 条绳子的长度。对于每条绳子，你可以将任意切割成一系列长度为 正整数 的部分，或者选择不进行切割。

例如，如果给你一条长度为 4 的绳子，你可以：

• 保持绳子的长度为 4 不变；
• 切割成一条长度为 3 和一条长度为 1 的绳子；
• 切割成两条长度为 2 的绳子；
• 切割成一条长度为 2 和两条长度为 1 的绳子；
• 切割成四条长度为 1 的绳子。

你的任务是找出最大 x 值，要求满足可以裁切出至少 k 条长度均为 x 的绳子。你可以丢弃裁切后剩余的任意长度的绳子。如果不可能切割出 k 条相同长度的绳子，返回 0。

 

示例 1:

输入: ribbons = [9,7,5], k = 3
输出: 5
解释:
- 把第一条绳子切成两部分，一条长度为 5，一条长度为 4；
- 把第二条绳子切成两部分，一条长度为 5，一条长度为 2；
- 第三条绳子不进行切割；
现在，你得到了 3 条长度为 5 的绳子。

示例 2:

输入: ribbons = [7,5,9], k = 4
输出: 4
解释:
- 把第一条绳子切成两部分，一条长度为 4，一条长度为 3；
- 把第二条绳子切成两部分，一条长度为 4，一条长度为 1；
- 把第二条绳子切成三部分，一条长度为 4，一条长度为 4，还有一条长度为 1；
现在，你得到了 4 条长度为 4 的绳子。

示例 3:

输入: ribbons = [5,7,9], k = 22
输出: 0
解释: 由于绳子长度需要为正整数，你无法得到 22 条长度相同的绳子。

 

提示:

• 1 <= ribbons.length <= 105
• 1 <= ribbons[i] <= 105
• 1 <= k <= 109

方法一：二分查找 · Go 实现

思考

绳子只能切短，求能得到至少 $k$ 段的最大等长。长度越大段数越少，具有单调性。

对长度在 $[0,maxribbons]$ 上二分：统计 $\sum \lfloor x/mid\rfloor$ 是否不少于 $k$。可行则尝试更长，否则缩短。

我们发现，如果我们能够得到长度为 $x$ 的 $k$ 根绳子，那么我们一定能够得到长度为 $x-1$ 的 $k$ 根绳子，这存在着单调性。因此，我们可以使用二分查找的方法，找到最大的长度 $x$，使得我们能够得到长度为 $x$ 的 $k$ 根绳子。

我们定义二分查找的左边界 $left=0$, $right=max(ribbons)$，中间值 $mid=(left+right+1)/2$，然后计算当前长度为 $mid$ 的绳子能够得到的数量 $cnt$，如果 $cnt\ge k$，说明我们能够得到长度为 $mid$ 的 $k$ 根绳子，那么我们将 $left$ 更新为 $mid$，否则我们将 $right$ 更新为 $mid-1$。

最后，我们返回 $left$ 即可。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别为绳子的数量和绳子的最大长度。空间复杂度 $O(1)$。

func maxLength(ribbons []int, k int) int {
	left, right := 0, slices.Max(ribbons)
	for left < right {
		mid := (left + right + 1) >> 1
		cnt := 0
		for _, x := range ribbons {
			cnt += x / mid
		}
		if cnt >= k {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

1894. 找到需要补充粉笔的学生编号

中等1 种解法

标签：数组、二分查找、前缀和、模拟

题目、示例与约束

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

 

示例 1：

输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

示例 2：

输入：chalk = [3,4,1,2], k = 25
输出：1
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。

 

提示：

• chalk.length == n
• 1 <= n <= 105
• 1 <= chalk[i] <= 105
• 1 <= k <= 109

方法一：求和取余 + 模拟 · Go 实现

思考

学生按编号循环消耗粉笔， $k$ 很大而一轮总和有限。直接模拟全部轮次会超时。

先对一轮总和取模，只保留最后不足一轮的粉笔。再从编号 $0$ 扫描，谁不够用谁就是答案。

由于学生的回答是一轮一轮循环进行的，因此我们可以将所有学生需要消耗的粉笔数加起来，得到一个总数 $s$。然后我们对 $k$ 取 $s$ 的余数，即可知道最后一轮结束后剩余的粉笔数。

接下来，我们只需要模拟最后一轮即可。初始时，剩余的粉笔数为 $k$，编号为 $0$ 的学生开始回答问题。当剩余的粉笔数小于当前学生需要的粉笔数时，当前学生需要补充粉笔，我们直接返回当前学生的编号 $i$ 即可。否则，我们将剩余的粉笔数减去当前学生需要的粉笔数，并将当前学生的编号 $i$ 加一，进行下一次模拟。

时间复杂度 $O(n)$，其中 $n$ 是学生的数量。空间复杂度 $O(1)$。

func chalkReplacer(chalk []int, k int) int {
	s := 0
	for _, x := range chalk {
		s += x
	}
	k %= s
	for i := 0; ; i++ {
		if k < chalk[i] {
			return i
		}
		k -= chalk[i]
	}
}

力扣原题 · Doocs 题解来源

1898. 可移除字符的最大数目

中等1 种解法

标签：数组、双指针、字符串、二分查找

题目、示例与约束

给你两个字符串 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 <= 105
• 0 <= removable.length < s.length
• 0 <= removable[i] < s.length
• p 是 s 的一个 子字符串
• s 和 p 都由小写英文字母组成
• removable 中的元素 互不相同

方法一：二分查找 · Go 实现

思考

按 $\mathit{\text{removable}}$ 的前缀依次删 $s$ 中的字符，求仍使 $p$ 为 $s$ 子序列的最长前缀。删除越多越难保持子序列，具有单调性。

对删除个数 $k$ 二分：标记前 $k$ 个下标后双指针判断 $p$ 是否仍为子序列。可行则增大 $k$。

我们注意到，如果移除 $\mathit{\text{removable}}$ 前 $k$ 个下标对应的字符后，满足 $p$ 仍然是 $s$ 的一个子序列，那么移除 $k<k^{\prime }\le \mathit{\text{removable.length}}$ 个下标对应的字符后，依然满足条件，这存在着单调性。因此，我们可以使用二分查找，找到最大的 $k$。

我们定义二分查找的左边界 $l=0$，右边界 $r=\mathit{\text{removable.length}}$，然后进行二分查找。在每次查找中，我们取中间值 $mid=\lfloor \frac{l+r+1}{2}\rfloor$，然后检查移除 $\mathit{\text{removable}}$ 的前 $mid$ 个下标对应的字符后，是否满足 $p$ 仍然是 $s$ 的一个子序列。如果满足，我们更新左边界 $l=mid$，否则更新右边界 $r=mid-1$。

二分查找结束后，返回左边界 $l$ 即可。

时间复杂度 $O(k\times \log k)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度，而 $k$ 是 $\mathit{\text{removable}}$ 的长度。

func maximumRemovals(s string, p string, removable []int) int {
	m, n := len(s), len(p)
	l, r := 0, len(removable)
	check := func(k int) bool {
		rem := make([]bool, m)
		for i := 0; i < k; i++ {
			rem[removable[i]] = true
		}
		i, j := 0, 0
		for i < m && j < n {
			if !rem[i] && s[i] == p[j] {
				j++
			}
			i++
		}
		return j == n
	}
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

力扣原题 · Doocs 题解来源

1901. 寻找峰值 II

中等1 种解法

标签：数组、二分查找、矩阵

题目、示例与约束

一个 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.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 105
• 任意两个相邻元素均不相等.

方法一：二分查找 · Go 实现

思考

逐格比较四邻可在 $O(mn)$ 内找出峰值，但题目要求 $O(n\log m)$ 或 $O(m\log n)$，全表扫描不满足时间限制。

若只看某一行的最大值 $mat[i][j]$，其与下一行使该列单调上升或下降，峰值必落在对应的半侧：向上则上半部分必有峰，向下则下半部分必有峰。反证可知，若该半侧无峰，边界处的行最大值将与外围 $-1$ 矛盾。

因此对行下标二分，每次在中行求最大值列 $j$，再与 $mat[mid+1][j]$ 比较以收缩区间。行数按对数收缩，每步扫描一列宽为 $n$ 的行，总时间为 $O(n\log m)$。

记 $m$ 和 $n$ 分别为矩阵的行数和列数。

题目要求我们寻找峰值，并且时间复杂度为 $O(m\times \log n)$ 或 $O(n\times \log m)$，那么我们可以考虑使用二分查找。

我们考虑第 $i$ 行的最大值，不妨将其下标记为 $j$。

如果 $mat[i][j]>mat[i+1][j]$，那么第 $[0,..i]$ 行中必然存在一个峰值，我们只需要在第 $[0,..i]$ 行中找到最大值即可。同理，如果 $mat[i][j]<mat[i+1][j]$，那么第 $[i+1,..m-1]$ 行中必然存在一个峰值，我们只需要在第 $[i+1,..m-1]$ 行中找到最大值即可。

为什么上述做法是对的？我们不妨用反证法来证明。

如果 $mat[i][j]>mat[i+1][j]$，假设第 $[0,..i]$ 行中不存在峰值，那么 $mat[i][j]$ 不是峰值，而由于 $mat[i][j]$ 是第 $i$ 行的最大值，并且 $mat[i][j]>mat[i+1][j]$，那么 $mat[i][j]<mat[i-1][j]$。我们继续从第 $i-1$ 行往上考虑，每一行的最大值都小于上一行的最大值。那么当遍历到 $i=0$ 时，由于矩阵中的元素都是正整数，并且矩阵周边一圈的格子的值都为 $-1$。因此，在第 $0$ 行时，其最大值大于其所有相邻元素，那么第 $0$ 行的最大值就是峰值，与假设矛盾。因此，第 $[0,..i]$ 行中必然存在一个峰值。

对于 $mat[i][j]<mat[i+1][j]$ 的情况，我们可以用类似的方法证明第 $[i+1,..m-1]$ 行中必然存在一个峰值。

因此，我们可以使用二分查找来寻找峰值。

我们二分查找矩阵的行，初始时查找的边界为 $l=0$, $r=m-1$。每一次，我们找到当前的中间行 $mid$，并找到该行的最大值下标 $j$。如果 $mat[mid][j]>mat[mid+1][j]$，那么我们就在第 $[0,..mid]$ 行中寻找峰值，即更新 $r=mid$。否则，我们就在第 $[mid+1,..m-1]$ 行中寻找峰值，即更新 $l=mid+1$。当 $l=r$ 时，我们就找到了峰值所在的位置 $[l,j_l]$。其中 $j_l$ 是第 $l$ 行的最大值下标。

时间复杂度 $O(n\times \log m)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。二分查找的时间复杂度为 $O(\log m)$，每次二分查找时，我们需要遍历第 $mid$ 行的所有元素，时间复杂度为 $O(n)$。空间复杂度 $O(1)$。

func findPeakGrid(mat [][]int) []int {
	maxPos := func(arr []int) int {
		j := 0
		for i := 1; i < len(arr); i++ {
			if arr[i] > arr[j] {
				j = i
			}
		}
		return j
	}
	l, r := 0, len(mat)-1
	for l < r {
		mid := (l + r) >> 1
		j := maxPos(mat[mid])
		if mat[mid][j] > mat[mid+1][j] {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return []int{l, maxPos(mat[l])}
}

力扣原题 · Doocs 题解来源

1918. 第 K 小的子数组和 🔒

中等1 种解法

标签：数组、二分查找、滑动窗口

题目、示例与约束

给你一个 长度为 n 的整型数组 nums 和一个数值 k ，返回 第 k 小的子数组和。

子数组 是指数组中一个 非空 且不间断的子序列。  子数组和 则指子数组中所有元素的和。

 

示例 1:

输入: nums = [2,1,3], k = 4
输出: 3
解释: [2,1,3] 的子数组为：
- [2] 和为 2
- [1] 和为 1
- [3] 和为 3
- [2,1] 和为 3
- [1,3] 和为 4
- [2,1,3] 和为 6 
最小子数组和的升序排序为 1, 2, 3, 3, 4, 6。 第 4 小的子数组和为 3 。

示例 2：

输入：nums = [3,3,5,5], k = 7
输出：10
解释：[3,3,5,5] 的子数组为：
- [3] 和为 3
- [3] 和为 3
- [5] 和为 5
- [5] 和为 5
- [3,3] 和为 6
- [3,5] 和为 8
- [5,5] 和为 10
- [3,3,5], 和为 11
- [3,5,5] 和为 13
- [3,3,5,5] 和为 16
最小子数组和的升序排序为 3, 3, 5, 5, 6, 8, 10, 11, 13, 16。第 7 小的子数组和为 10 。

 

提示:

• n == nums.length
• 1 <= n <= 2 * 104
• 1 <= nums[i] <= 5 * 104
• 1 <= k <= n * (n + 1) / 2

方法一：二分查找 + 双指针 · Go 实现

思考

子数组有 $O(n^2)$ 个，全部求出再选第 $k$ 小在 $n\le 2\times {10}^4$ 时空间与时间都紧张。元素均为正，子数组和具有单调性。

和不超过 $s$ 的子数组个数随 $s$ 不减。二分 $s$，用双指针在线性时间内统计个数，与 $k$ 比较以收缩区间。

左端取数组最小值、右端取总和，二分结束后左界即为第 $k$ 小和。

我们注意到，题目中数组元素均为正整数，子数组的和 $s$ 越大，那么数组中子数组和小于等于 $s$ 的个数就越多。这存在一个单调性，因此我们可以考虑使用使用二分查找的方法来求解。

我们二分枚举子数组的和，初始化左右边界分别为数组 $\mathit{\text{nums}}$ 中的最小值以及所有元素之和。每次我们计算数组中子数组和小于等于当前枚举值的个数，如果个数大于等于 $k$，则说明当前枚举值 $s$ 可能是第 $k$ 小的子数组和，我们缩小右边界，否则我们增大左边界。枚举结束后，左边界即为第 $k$ 小的子数组和。

问题转换为计算一个数组中，有多少个子数组的和小于等于 $s$，我们可以通过函数 $f(s)$ 来计算。

函数 $f(s)$ 的计算方法如下：

• 初始化双指针 $j$ 和 $i$，分别指向当前窗口的左右边界，初始时 $j=i=0$。初始化窗口内元素的和 $t=0$。
• 用变量 $\mathit{\text{cnt}}$ 记录子数组和小于等于 $s$ 的个数，初始时 $\mathit{\text{cnt}}=0$。
• 遍历数组 $\mathit{\text{nums}}$，每次遍历到一个元素 $\mathit{\text{nums}}[i]$，我们将其加入窗口，即 $t=t+\mathit{\text{nums}}[i]$。如果此时 $t>s$，我们需要不断地将窗口的左边界右移，直到 $t\le s$ 为止，即不断地执行 $t-=\mathit{\text{nums}}[j]$，并且 $j=j+1$。接下来我们更新 $\mathit{\text{cnt}}$，即 $\mathit{\text{cnt}}=\mathit{\text{cnt}}+i-j+1$。继续遍历下一个元素，直到遍历完整个数组。

最后将 $cnt$ 作为函数 $f(s)$ 的返回值。

时间复杂度 $O(n\times \log S)$，其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度，而 $S$ 为数组 $\mathit{\text{nums}}$ 中所有元素之和。空间复杂度 $O(1)$。

func kthSmallestSubarraySum(nums []int, k int) int {
	l, r := 1<<30, 0
	for _, x := range nums {
		l = min(l, x)
		r += x
	}
	f := func(s int) (cnt int) {
		t := 0
		for i, j := 0, 0; i < len(nums); i++ {
			t += nums[i]
			for t > s {
				t -= nums[j]
				j++
			}
			cnt += i - j + 1
		}
		return
	}
	for l < r {
		mid := (l + r) >> 1
		if f(mid) >= k {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

力扣原题 · Doocs 题解来源

1923. 最长公共子路径

困难1 种解法

标签：数组、二分查找、后缀数组、哈希函数、滚动哈希

题目、示例与约束

一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里，每两个 城市之间都有一条道路连接。

总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 重复 出现，但同一个城市在一条路径中不会连续出现。

给你一个整数 n 和二维数组 paths ，其中 paths[i] 是一个整数数组，表示第 i 个朋友走过的路径，请你返回 每一个 朋友都走过的 最长公共子路径 的长度，如果不存在公共子路径，请你返回 0 。

一个 子路径 指的是一条路径中连续的城市序列。

 

示例 1：

输入：n = 5, paths = [[0,1,2,3,4],
                     [2,3,4],
                     [4,0,1,2,3]]
输出：2
解释：最长公共子路径为 [2,3] 。

示例 2：

输入：n = 3, paths = [[0],[1],[2]]
输出：0
解释：三条路径没有公共子路径。

示例 3：

输入：n = 5, paths = [[0,1,2,3,4],
                     [4,3,2,1,0]]
输出：1
解释：最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。

 

提示：

• 1 <= n <= 105
• m == paths.length
• 2 <= m <= 105
• sum(paths[i].length) <= 105
• 0 <= paths[i][j] < n
• paths[i] 中同一个城市不会连续重复出现。

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：在各条路径前加入题目中不存在的分隔值，拼接后把每个整数编码成四字节，调用 Go 后缀数组库，并只保留整数边界上的后缀。计算相邻后缀的最长公共前缀长度，再二分公共子路径长度。检查时扫描公共前缀长度达到阈值的连续后缀块，利用路径编号和访问标记判断其中是否覆盖全部路径。

复杂度：设路径数为 p，所有路径元素总数为 T，N=T+p 为加入分隔符后的长度，L 为最短路径长度。按 Go 标准库的线性后缀数组构建实现，预处理 O(N)，每次检查 O(N+p)，总时间为 O(N log(L+1))，辅助空间为 O(N)。源码通过 reflect/unsafe 读取后缀数组内部字段，依赖 Go 标准库的内部布局。

import (
	"index/suffixarray"
	"reflect"
	"sort"
	"unsafe"
)

// github.com/EndlessCheng/codeforces-go
func longestCommonSubpath(_ int, paths [][]int) (ans int) {
	a := []int{}
	minLen := int(1e9) // 二分右边界
	for _, p := range paths {
		minLen = min(minLen, len(p))
		a = append(a, 1e9) // 用一个不存在 paths 中的数拼接所有路径
		a = append(a, p...)
	}
	n, m := len(a), len(paths)

	// 标记每个元素属于哪条路径
	ids := make([]int, n)
	id := -1
	for i, v := range a {
		if v == 1e9 {
			id++
			ids[i] = m
		} else {
			ids[i] = id
		}
	}

	// 构建 a 的后缀数组和高度数组
	s := make([]byte, 0, n*4)
	for _, v := range a {
		s = append(s, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
	}
	_sa := *(*[]int32)(unsafe.Pointer(reflect.ValueOf(suffixarray.New(s)).Elem().FieldByName("sa").Field(0).UnsafeAddr()))
	sa := make([]int32, 0, n)
	for _, v := range _sa {
		if v&3 == 0 {
			sa = append(sa, v>>2)
		}
	}
	rank := make([]int, n)
	for i := range rank {
		rank[sa[i]] = i
	}
	height := make([]int, n)
	h := 0
	for i, rk := range rank {
		if h > 0 {
			h--
		}
		if rk > 0 {
			for j := int(sa[rk-1]); i+h < n && j+h < n && a[i+h] == a[j+h]; h++ {
			}
		}
		height[rk] = h
	}

	// 二分求答案
	return sort.Search(minLen, func(limit int) bool {
		limit++
		vis := make([]int, m)
		for i := 1; i < n; i++ {
			if height[i] < limit {
				continue
			}
			cnt := 0
			for st := i; i < n && height[i] >= limit; i++ {
				// 检查 sa[i] 和 sa[i-1]
				if j := ids[sa[i]]; j < m && vis[j] != st {
					vis[j] = st
					cnt++
				}
				if j := ids[sa[i-1]]; j < m && vis[j] != st {
					vis[j] = st
					cnt++
				}
			}
			// 连续 m 个属于不同路径的后缀长度均不小于 limit
			if cnt == m {
				return false
			}
		}
		return true
	})
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

力扣原题 · Doocs 题解来源

1954. 收集足够苹果的最小花园周长

中等2 种解法

标签：数学、二分查找

题目、示例与约束

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。

你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。

给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。

|x| 的值定义为：

• 如果 x >= 0 ，那么值为 x
• 如果 x < 0 ，那么值为 -x

 

示例 1：

输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。

示例 2：

输入：neededApples = 13
输出：16

示例 3：

输入：neededApples = 1000000000
输出：5040

 

提示：

• 1 <= neededApples <= 1015

方法一：数学 + 枚举 · Go 实现

思考

边长为 $2x$ 的正方形内苹果数为 $2x(x+1)(2x+1)$，周长为 $8x$。 $neededApples$ 很大，但 $x$ 只需立方根量级。

自 $x=1$ 递增直到公式达到需求，返回 $8x$。

假设正方形右上角坐标为 $(n,n)$，那么它的边长为 $2n$，周长为 $8n$，里面的苹果总数为：

$$\begin{array}{rl}& \sum _{x=-n}^n\sum _{y=-n}^n|x|+|y|\end{array}$$

由于 $x$ 和 $y$ 是对称的，所以可以化简为：

$$\begin{array}{rl}& \sum _{x=-n}^n\sum _{y=-n}^n|x|+|y|\\ & =2\sum _{x=-n}^n\sum _{y=-n}^n|x|\\ & =2\sum _{x=-n}^n(2n+1)|x|\\ & =2(2n+1)\sum _{x=-n}^n|x|\\ & =2n(n+1)(2n+1)\end{array}$$

所以，我们只需要枚举 $n$，直到找到第一个满足 $2n(n+1)(2n+1)\ge neededApples$ 的 $n$ 即可。

时间复杂度 $O(m^{\frac{1}{3}})$，其中 $m$ 为 $neededApples$ 的值。空间复杂度 $O(1)$。

func minimumPerimeter(neededApples int64) int64 {
	var x int64 = 1
	for 2*x*(x+1)*(2*x+1) < neededApples {
		x++
	}
	return 8 * x
}

方法二：二分查找 · Go 实现

思考

线性递增在最坏情况下步数仍随立方根增长。公式对 $x$ 单调，可在 $[1,{10}^5]$ 上二分最小可行 $x$，再乘 $8$。

我们也可以二分枚举 $n$，时间复杂度 $O(\log m)$。

func minimumPerimeter(neededApples int64) int64 {
	var l, r int64 = 1, 100000
	for l < r {
		mid := (l + r) >> 1
		if 2*mid*(mid+1)*(2*mid+1) >= neededApples {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l * 8
}

力扣原题 · Doocs 题解来源

1956. 感染 K 种病毒所需的最短时间 🔒

困难1 种解法

标签：几何、数组、数学、二分查找、枚举、有序集合、滑动窗口

题目、示例与约束

在无限大的二维平面上有 n 种 不同 的病毒。给定二维数组 points ，第 i 项 points[i] = [xi, yi] 说明第 0 天有一种病毒在点 (xi, yi) 。注意初始状态下，可能有 多种 病毒在 同一点 上。

每天，被感染的点会把它感染的病毒传播到上、下、左、右四个邻居点。

现给定一个整数 k ，问 最少 需要多少天，方能找到一点感染 至少 k 种病毒？

 

示例 1：

输入：points = [[1,1],[6,1]], k = 2
输出：3
解释：在第 3 天，点 (3,1) 与 (4,1) 将感染所有 2 种病毒。

示例 2：

输入：points = [[3,3],[1,2],[9,2]], k = 2
输出：2
解释：在第 2 天, 点 (1,2), (1,3), (2,1), (2,2), (3,1) 和 (3,3) 将会感染前两种病毒。

示例 3：

输入：points = [[3,3],[1,2],[9,2]], k = 3
输出：4
解释：在第 4 天，点 (5,2) 会感染所有 3 种病毒。

 

提示：

• n == points.length
• 2 <= n <= 50
• points[i].length == 2
• 1 <= xi, yi <= 109
• 2 <= k <= n

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

根据题意整理：源文只有坐标变换思考，没有非空实现。将点变为 u=x+y、v=x-y，曼哈顿半径 t 对应两个轴上半径 t 的闭区间。合法格点要求 u、v 同奇偶。对两种奇偶分别枚举各区间左端向该奇偶对齐后的 u、v，统计覆盖数是否至少 k；若存在交叠，其交集最小合法坐标必在这些候选中，因此判定完整。二分最小 t；不能省略奇偶约束。n 为变体数，C 为坐标跨度上界，时间 O(n³ log C)，n≤50；空间 O(n)。内部坐标与时间均用 int64，入口 minDayskVariants。

出处：Doocs 原题与题解，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；题意、参考及本 Go 改写采用 CC BY-SA 4.0。

// 题意与参考：Doocs LeetCode，CC BY-SA 4.0。
// https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1900-1999/1956.Minimum%20Time%20For%20K%20Virus%20Variants%20to%20Spread/README.md
// Go 实现与测试沿用 CC BY-SA 4.0；来源性质见配套说明。
func minDayskVariants(points [][]int, k int) int {
	n := len(points)
	u, v := make([]int64, n), make([]int64, n)
	for i, p := range points {
		u[i] = int64(p[0]) + int64(p[1])
		v[i] = int64(p[0]) - int64(p[1])
	}
	abs := func(x int64) int64 {
		if x < 0 {
			return -x
		}
		return x
	}
	feasible := func(t int64) bool {
		for parity := int64(0); parity < 2; parity++ {
			for _, a := range u {
				x := a - t
				if x&1 != parity {
					x++
				}
				for _, b := range v {
					y := b - t
					if y&1 != parity {
						y++
					}
					count := 0
					for i := 0; i < n; i++ {
						if abs(x-u[i]) <= t && abs(y-v[i]) <= t {
							count++
							if count >= k {
								return true
							}
						}
					}
				}
			}
		}
		return false
	}
	lo, hi := int64(0), int64(2000000000)
	for lo < hi {
		mid := (lo + hi) / 2
		if feasible(mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	return int(lo)
}

力扣原题 · Doocs 题解来源

1966. 未排序数组中的可被二分查找的数 🔒

中等1 种解法

标签：栈、数组、二分查找、单调栈

题目、示例与约束

有一个 类似 二分查找 的方法。 这个方法有两个入参: sequence 是一个整数数组， target 是一个整数。 这个方法可以判断 target 是否存在 sequence中。

该方法的伪代码如下：

func(sequence, target)
  while sequence is not empty
    randomly choose an element from sequence as the pivot
    if pivot = target, return true
    else if pivot < target, remove pivot and all elements to its left from the sequence
    else, remove pivot and all elements to its right from the sequence
  end while
  return false

当 sequence 是排好序时, 这个方法对 所有 值都可正常判断。如果 sequence 不是排好序的, 该方法并不是对所有值都可正常判断, 但对一些 值仍可正常判断。

给定一个仅包含不同数字的数组 nums表示 sequence， nums是否排序未知，对于 所有可能的选择, 返回通过这个方法保证能找到的值的数量。

 

示例 1:

输入: nums = [7]
输出: 1
解释: 
7 保证能被找到.
因为数组中只有一个数字, 7 一定会被选中. 因为选中的值等于target, 这个方法会返回 true.

示例 2:

输入: nums = [-1,5,2]
输出: 1
解释: 
只有 -1 保证能被找到.
如果 -1 被选中, 这个方法就会返回 true.
如果 5 被选中, 5 和 2 会被移除。 在下一次循环时, 这个序列只有一个元素： -1 ，这个方法就会返回 true.
如果 2 被选中, 2 将会被移除。 在下次循环时, 这个序列里将会有 -1 和 5. 无论哪个数字被选中, 这个方法都会找到 -1 且返回 true.

5 不能保证被找到。
如果 2 被选中, -1, 5 和 2 将会被移除。 这个序列将会被清空且这个方法会返回 false。

2 不能保证被找到.
如果 5 被选中, 5 和 2 将会被移除。在下次循环时, 这个序列只会有一个元素： -1 且这个方法会返回 false。

因为只有-1 是保证能被找到的, 你应该返回 1.

 

提示:

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• nums 中所有值都 不同.

 

提升: 如果 nums 存在 重复的值, 你会如何修改你的算法吗? 

方法一：维护前缀最大值和后缀最小值 · Go 实现

思考

二分每次丢弃中点一侧。一个值能被搜到，必须大于左侧所有值且小于右侧所有值，否则错误的一半可能被丢掉。

从左维护前缀最大，从右维护后缀最小，两遍标记不满足者，最后统计仍合法的个数。

我们注意到，对于数组中的每个元素，如果它是可被二分搜索的，那么需要满足两个条件：

1. 这个元素大于它的左边所有元素，否则，如果左边存在比当前元素大的元素，那么就会被移除，导致无法找到当前元素；
2. 这个元素小于它的右边所有元素，否则，如果右边存在比当前元素小的元素，那么就会被移除，导致无法找到当前元素。

我们创建一个数组 $ok$，其中 $ok[i]$ 表示 $nums[i]$ 是否是可被二分搜索的。初始时 $ok[i]$ 都为 $1$。

我们先从左到右遍历数组，维护前缀最大值 $mx$，如果当前元素 $x$ 比 $mx$ 小，那么 $x$ 就不是可被二分搜索的，我们将 $ok[i]$ 置为 $0$，否则，我们将 $mx$ 更新为 $x$。

然后我们从右到左遍历数组，维护后缀最小值 $mi$，如果当前元素 $x$ 比 $mi$ 大，那么 $x$ 就不是可被二分搜索的，我们将 $ok[i]$ 置为 $0$，否则，我们将 $mi$ 更新为 $x$。

最后我们统计 $ok$ 中的 $1$ 的个数，即为可被二分搜索的元素的个数。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

func binarySearchableNumbers(nums []int) (ans int) {
	n := len(nums)
	ok := make([]int, n)
	for i := range ok {
		ok[i] = 1
	}
	mx, mi := -1000000, 1000000
	for i, x := range nums {
		if x < mx {
			ok[i] = 0
		} else {
			mx = x
		}
	}
	for i := n - 1; i >= 0; i-- {
		if nums[i] > mi {
			ok[i] = 0
		} else {
			mi = nums[i]
		}
		ans += ok[i]
	}
	return
}

力扣原题 · Doocs 题解来源

2009. 使数组连续的最少操作数

困难2 种解法

标签：数组、哈希表、二分查找、滑动窗口

题目、示例与约束

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

• nums 中所有元素都是 互不相同 的。
• nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

 

示例 1：

输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。

示例 2：

输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。

示例 3：

输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

方法一：排序 + 去重 + 二分查找 · Go 实现

思考

连续数组的值域长度为 $n$，重复元素必须改掉。 $n\le {10}^5$，不能枚举每个目标区间。去重排序后，合法窗口是「最大值与最小值之差 $\le n-1$」的一段原有数。

枚举窗口左端 $nums[i]$，则右端不得超过 $nums[i]+n-1$。二分找到第一个越界位置 $j$， $j-i$ 即保留个数，操作为 $n-(j-i)$。

排序决定复杂度，查询为 $O(\log n)$。

我们先将数组排序，去重。

然后遍历数组，枚举以当前元素 $nums[i]$ 作为连续数组的最小值，通过二分查找找到第一个大于 $nums[i]+n-1$ 的位置 $j$，那么 $j-i$ 就是当前元素作为最小值时，连续数组的长度，更新答案，即 $ans=min(ans,n-(j-i))$。

最后返回 $ans$ 即可。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

func minOperations(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	m := 1
	for i := 1; i < n; i++ {
		if nums[i] != nums[i-1] {
			nums[m] = nums[i]
			m++
		}
	}
	ans := n
	for i := 0; i < m; i++ {
		j := sort.Search(m, func(k int) bool { return nums[k] > nums[i]+n-1 })
		ans = min(ans, n-(j-i))
	}
	return ans
}

方法二：排序 + 去重 + 双指针 · Go 实现

思考

方法一每次用二分定位右端，窗口随 $i$ 右移时右端也单调右移，不必重复折半。

为此用双指针推进 $j$，在同样 $O(n)$ 扫描内得到所有窗口，省去二分的对数因子。

与方法一类似，我们先将数组排序，去重。

然后遍历数组，枚举以当前元素 $nums[i]$ 作为连续数组的最小值，通过双指针找到第一个大于 $nums[i]+n-1$ 的位置 $j$，那么 $j-i$ 就是当前元素作为最小值时，连续数组的长度，更新答案，即 $ans=min(ans,n-(j-i))$。

最后返回 $ans$ 即可。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

func minOperations(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	m := 1
	for i := 1; i < n; i++ {
		if nums[i] != nums[i-1] {
			nums[m] = nums[i]
			m++
		}
	}
	ans := n
	for i, j := 0, 0; i < m; i++ {
		for j < m && nums[j]-nums[i] <= n-1 {
			j++
		}
		ans = min(ans, n-(j-i))
	}
	return ans
}

力扣原题 · Doocs 题解来源

2024. 考试的最大困扰度

中等1 种解法

标签：字符串、二分查找、前缀和、滑动窗口

题目、示例与约束

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

• 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

 

示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。

 

提示：

• n == answerKey.length
• 1 <= n <= 5 * 104
• answerKey[i] 要么是 'T' ，要么是 'F'
• 1 <= k <= n

方法一：滑动窗口 · Go 实现

思考

最多改 $k$ 个位置，使最长连续段最大。 $n\le 5\times {10}^4$，不能枚举每个区间再数修改次数。改成全 T 与全 F 互不影响，可分别求。

窗口内「异类」个数不超过 $k$ 时，窗口即可变成目标字符。右端右移，超额则左端右移。

两次滑动窗口取较大长度。代码中窗口始终合法，长度为 $n-l$。

我们设计一个函数 $\mathit{\text{f}}(c)$，表示最多替换 $k$ 个字符 $c$ 的情况下，最长的连续字符的长度，其中 $c$ 可以是 'T' 或 'F'。答案就是 $max(\mathit{\text{f}}{(}^{\prime }{T}^{\prime }),\mathit{\text{f}}{(}^{\prime }{F}^{\prime }))$。

我们遍历字符串 $\mathit{\text{answerKey}}$，用一个变量 $\mathit{\text{cnt}}$ 记录当前窗口内字符 $c$ 的个数，当 $\mathit{\text{cnt}}>k$ 时，我们将窗口的左指针右移一位。遍历结束后，窗口的长度即为最大连续字符的长度。

时间复杂度 $O(n)$，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$。

相似题目：

• 487. 最大连续 1 的个数 II
• 1004. 最大连续 1 的个数 III

func maxConsecutiveAnswers(answerKey string, k int) int {
	f := func(c byte) int {
		l, cnt := 0, 0
		for _, ch := range answerKey {
			if byte(ch) == c {
				cnt++
			}
			if cnt > k {
				if answerKey[l] == c {
					cnt--
				}
				l++
			}
		}
		return len(answerKey) - l
	}
	return max(f('T'), f('F'))
}

力扣原题 · Doocs 题解来源

2040. 两个有序数组的第 K 小乘积

困难1 种解法

标签：数组、二分查找

题目、示例与约束

给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] * nums2[j] 的乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。

 

示例 1：

输入：nums1 = [2,5], nums2 = [3,4], k = 2
输出：8
解释：第 2 小的乘积计算如下：
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
第 2 小的乘积为 8 。

示例 2：

输入：nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
输出：0
解释：第 6 小的乘积计算如下：
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
第 6 小的乘积为 0 。

示例 3：

输入：nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
输出：-6
解释：第 3 小的乘积计算如下：
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
第 3 小的乘积为 -6 。

 

提示：

• 1 <= nums1.length, nums2.length <= 5 * 104
• -105 <= nums1[i], nums2[j] <= 105
• 1 <= k <= nums1.length * nums2.length
• nums1 和 nums2 都是从小到大排好序的。

方法一：二分查找 · Go 实现

思考

两数组有序，乘积共可达 $2.5\times {10}^9$ 个，不能物化。第 $k$ 小对阈值单调：乘积 $\le p$ 的个数随 $p$ 不减。

在 $[-M,M]$ 上二分 $p$，计数时对 $nums1$ 的每个 $x$ 分类：正数则 $nums2[i]\le p/x$，负数则不等式反向，零则视 $p$ 是否非负。有序保证可用二分完成计数。

bisect_left 找到最小使计数 $\ge k$ 的 $p$。

我们可以二分枚举乘积的值 $p$，定义二分的区间为 $[l,r]$，其中 $l=-\mathit{\text{max}}(|\mathit{\text{nums1}}[0]|,|\mathit{\text{nums1}}[n-1]|)\times \mathit{\text{max}}(|\mathit{\text{nums2}}[0]|,|\mathit{\text{nums2}}[n-1]|)$, $r=-l$。

对于每个 $p$，我们计算出乘积小于等于 $p$ 的乘积的个数，如果这个个数大于等于 $k$，那么说明第 $k$ 小的乘积一定小于等于 $p$，我们就可以将区间右端点缩小到 $p$，否则我们将区间左端点增大到 $p+1$。

那么问题的关键就是如何计算乘积小于等于 $p$ 的乘积的个数。我们可以枚举 $\mathit{\text{nums1}}$ 中的每个数 $x$，分类讨论：

• 如果 $x>0$，那么 $x\times \mathit{\text{nums2}}[i]$ 随着 $i$ 的增大是单调递增的，我们可以使用二分查找找到最小的 $i$，使得 $x\times \mathit{\text{nums2}}[i]>p$，那么 $i$ 就是小于等于 $p$ 的乘积的个数，累加到个数 $\mathit{\text{cnt}}$ 中；
• 如果 $x<0$，那么 $x\times \mathit{\text{nums2}}[i]$ 随着 $i$ 的增大是单调递减的，我们可以使用二分查找找到最小的 $i$，使得 $x\times \mathit{\text{nums2}}[i]\le p$，那么 $n-i$ 就是小于等于 $p$ 的乘积的个数，累加到个数 $\mathit{\text{cnt}}$ 中；
• 如果 $x=0$，那么 $x\times \mathit{\text{nums2}}[i]=0$，如果 $p\ge 0$，那么 $n$ 就是小于等于 $p$ 的乘积的个数，累加到个数 $\mathit{\text{cnt}}$ 中。

这样我们就可以通过二分查找找到第 $k$ 小的乘积。

时间复杂度 $O(m\times \log n\times \log M)$，其中 $m$ 和 $n$ 分别为 $\mathit{\text{nums1}}$ 和 $\mathit{\text{nums2}}$ 的长度，而 $M$ 为 $\mathit{\text{nums1}}$ 和 $\mathit{\text{nums2}}$ 中的最大值的绝对值。

func kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {
	m := len(nums1)
	n := len(nums2)
	a := max(abs(nums1[0]), abs(nums1[m-1]))
	b := max(abs(nums2[0]), abs(nums2[n-1]))
	r := int64(a) * int64(b)
	l := -r

	count := func(p int64) int64 {
		var cnt int64
		for _, x := range nums1 {
			if x > 0 {
				l, r := 0, n
				for l < r {
					mid := (l + r) >> 1
					if int64(x)*int64(nums2[mid]) > p {
						r = mid
					} else {
						l = mid + 1
					}
				}
				cnt += int64(l)
			} else if x < 0 {
				l, r := 0, n
				for l < r {
					mid := (l + r) >> 1
					if int64(x)*int64(nums2[mid]) <= p {
						r = mid
					} else {
						l = mid + 1
					}
				}
				cnt += int64(n - l)
			} else if p >= 0 {
				cnt += int64(n)
			}
		}
		return cnt
	}

	for l < r {
		mid := (l + r) >> 1
		if count(mid) >= k {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

2055. 蜡烛之间的盘子

中等1 种解法

标签：数组、字符串、二分查找、前缀和

题目、示例与约束

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

• 比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。

请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

 

示例 1:

输入：s = "**|**|***|", queries = [[2,5],[5,9]]
输出：[2,3]
解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

示例 2:

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出：[9,0,0,0,0]
解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

 

提示：

• 3 <= s.length <= 105
• s 只包含字符 '*' 和 '|' 。
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= lefti <= righti < s.length

方法一 · Go 实现

思考

询问次数与串长均为 ${10}^5$，不能对每个区间再扫盘子。一段盘子被计入当且仅当左右都有蜡烛夹住。

盘子前缀和给出任意开区间内的 * 个数；再预处理每个位置左侧最近与右侧最近的 |。询问 $[l,r]$ 取右侧第一根蜡烛 $i$ 与左侧最后一根 $j$，若 $i<j$ 则答案为 $presum[j]-presum[i+1]$。

func platesBetweenCandles(s string, queries [][]int) []int {
	n := len(s)
	presum := make([]int, n+1)
	for i := range s {
		if s[i] == '*' {
			presum[i+1] = 1
		}
		presum[i+1] += presum[i]
	}
	left, right := make([]int, n), make([]int, n)
	for i, l := 0, -1; i < n; i++ {
		if s[i] == '|' {
			l = i
		}
		left[i] = l
	}
	for i, r := n-1, -1; i >= 0; i-- {
		if s[i] == '|' {
			r = i
		}
		right[i] = r
	}
	ans := make([]int, len(queries))
	for k, q := range queries {
		i, j := right[q[0]], left[q[1]]
		if i >= 0 && j >= 0 && i < j {
			ans[k] = presum[j] - presum[i+1]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2070. 每一个查询的最大美丽值

中等2 种解法

标签：数组、二分查找、排序

题目、示例与约束

给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。

同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。

请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

 

示例 1：

输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
输出：[2,4,5,5,6,6]
解释：
- queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
  它们中的最大美丽值为 4 。
- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
  它们中的最大美丽值为 5 。
- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
  所以，答案为所有物品中的最大美丽值，为 6 。

示例 2：

输入：items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
输出：[4]
解释：
每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。
注意，多个物品可能有相同的价格和美丽值。

示例 3：

输入：items = [[10,1000]], queries = [5]
输出：[0]
解释：
没有物品的价格小于等于 5 ，所以没有物品可以选择。
因此，查询的结果为 0 。

 

提示：

• 1 <= items.length, queries.length <= 105
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 109

方法一：排序 + 离线查询 · Go 实现

思考

每个查询要价格 $\le q$ 的最大美丽值。 $n,m\le {10}^5$，在线对每个 $q$ 扫描物品不可行。离线后查询与物品都按价格升序，指针只向前。

扫到价格不超过当前 $q$ 的物品时更新美丽最大值，写入对应下标。排序决定复杂度。

对于每一个查询，我们需要找到价格小于等于查询价格的物品中的最大美丽值，我们不妨采用离线查询的方式，先对物品按价格排序，然后对查询按照价格排序。

接下来，我们从小到大遍历查询，对于每一个查询，我们用一个指针 $i$ 指向物品数组，如果物品的价格小于等于查询价格，我们更新当前的最大美丽值，向右移动指针 $i$，直到物品的价格大于查询价格，我们将当前的最大美丽值记录下来，就是当前查询的答案。继续遍历下一个查询，直到所有的查询都处理完。

时间复杂度 $O(n\times \log n+m\times \log m)$，空间复杂度 $O(\log n+m)$。其中 $n$ 和 $m$ 分别为物品数组和查询数组的长度。

func maximumBeauty(items [][]int, queries []int) []int {
	sort.Slice(items, func(i, j int) bool {
		return items[i][0] < items[j][0]
	})
	n, m := len(items), len(queries)
	idx := make([]int, m)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return queries[idx[i]] < queries[idx[j]] })
	ans := make([]int, m)
	i, mx := 0, 0
	for _, j := range idx {
		for i < n && items[i][0] <= queries[j] {
			mx = max(mx, items[i][1])
			i++
		}
		ans[j] = mx
	}
	return ans
}

方法二：排序 + 二分查找 · Go 实现

思考

方法一打乱查询顺序。若需在线回答，可在物品按价格排序后预处理「不超过该价的最大美丽」，再对每个 $q$ 二分。

mx 数组单调，bisect_right 找到最后一个可买下标。

我们可以将物品按照价格排序，然后预处理出小于等于每个价格的物品中的最大美丽值，记录在数组 $mx$ 或者原 $items$ 数组中。

对于每一个查询，我们可以使用二分查找找到第一个价格大于查询价格的物品的下标 $j$，然后 $j-1$ 就是小于等于查询价格且最大美丽值的物品的下标，添加到答案中。

时间复杂度 $O((m+n)\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为物品数组和查询数组的长度。

func maximumBeauty(items [][]int, queries []int) []int {
	sort.Slice(items, func(i, j int) bool {
		return items[i][0] < items[j][0]
	})
	n, m := len(items), len(queries)
	prices := make([]int, n)
	prices[0] = items[0][0]
	for i := 1; i < n; i++ {
		prices[i] = items[i][0]
		items[i][1] = max(items[i][1], items[i-1][1])
	}
	ans := make([]int, m)
	for i, q := range queries {
		j := sort.SearchInts(prices, q+1) - 1
		if j >= 0 {
			ans[i] = items[j][1]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2089. 找出数组排序后的目标下标

简单2 种解法

标签：数组、二分查找、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。

目标下标 是一个满足 nums[i] == target 的下标 i 。

将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列。

 

示例 1：

输入：nums = [1,2,5,2,3], target = 2
输出：[1,2]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 2 的下标是 1 和 2 。

示例 2：

输入：nums = [1,2,5,2,3], target = 3
输出：[3]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 3 的下标是 3 。

示例 3：

输入：nums = [1,2,5,2,3], target = 5
输出：[4]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 5 的下标是 4 。

示例 4：

输入：nums = [1,2,5,2,3], target = 4
输出：[]
解释：nums 中不含值为 4 的元素。

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i], target <= 100

方法一：排序 · Go 实现

思考

$n\le 100$，排序后收集等于 $target$ 的下标。下标已按升序产生。

若需线性时间，也可数更小值个数与相等个数，再生成区间；当前实现直接排序。

将数组 nums 排序后，遍历数组，找出所有等于 target 的元素的下标，将其加入结果数组中。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 nums 的长度。

func targetIndices(nums []int, target int) (ans []int) {
	sort.Ints(nums)
	for i, v := range nums {
		if v == target {
			ans = append(ans, i)
		}
	}
	return
}

方法二：计数 · Go 实现

思考

方法一为了得到下标，先对整个数组做比较排序，时间停在 $O(n\log n)$。返回的下标只由 $target$ 在有序序列中的位置决定，其它元素彼此的先后并不影响答案。

严格小于 $target$ 的个数就是这段连续下标的起点，等于 $target$ 的个数就是区间长度。这两个量在原数组上各计一次即可，不必再比较元素的相对次序，因此用一次扫描代替排序。

等于 $target$ 的元素在非递减排序后占据一段连续下标。这段下标的起点等于数组中严格小于 $target$ 的元素个数，长度等于等于 $target$ 的元素个数。

遍历一次 $\mathit{\text{nums}}$，分别用 $\mathit{\text{less}}$、 $\mathit{\text{equal}}$ 统计这两类元素。答案就是区间 $[\mathit{\text{less}},\mathit{\text{less}}+\mathit{\text{equal}})$ 中的全部整数。 $\mathit{\text{equal}}=0$ 时区间为空。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func targetIndices(nums []int, target int) (ans []int) {
	less, equal := 0, 0
	for _, x := range nums {
		if x < target {
			less++
		} else if x == target {
			equal++
		}
	}
	for i := less; i < less+equal; i++ {
		ans = append(ans, i)
	}
	return
}

力扣原题 · Doocs 题解来源

2106. 摘水果

困难1 种解法

标签：数组、二分查找、前缀和、滑动窗口

题目、示例与约束

在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。

另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的 最大总数 。

 

示例 1：

输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果

示例 2：

输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出：14
解释：
可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果

示例 3：

输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出：0
解释：
最多可以移动 k = 2 步，无法到达任一有水果的地方

 

提示：

• 1 <= fruits.length <= 105
• fruits[i].length == 2
• 0 <= startPos, positioni <= 2 * 105
• 对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）
• 1 <= amounti <= 104
• 0 <= k <= 2 * 105

方法一：双指针 · Go 实现

思考

水果位置有序，最优路线必是某一闭区间 $[l,r]$：先走到较近端再折返覆盖另一端，步数为 $r-l+min(|\mathit{\text{startPos}}-l|,|r-\mathit{\text{startPos}}|)$。若枚举全部端点再求和，区间数为 $O(n^2)$，在 $n\le {10}^5$ 时不可行。

固定右端 $r$ 并将左端右移时，该步数单调不增，因此可用双指针找到所有步数不超过 $k$ 的最大窗口，窗口内水果量和随指针增减维护。

为此用 $i$、 $j$ 扫描 $\mathit{\text{fruits}}$，累加 $s$，当区间步数超过 $k$ 时右移 $i$ 并减去左侧水果，同时记录 $s$ 的最大值。

我们不妨假设移动的位置区间为 $[l,r]$，开始位置为 $\mathit{\text{startPos}}$，来看看如何算出移动的最小步数。根据 $\mathit{\text{startPos}}$ 所处的位置，我们可以分为三种情况：

1. 如果 $\mathit{\text{startPos}}\le l$，那么就是从 $\mathit{\text{startPos}}$ 一直向右移动到 $r$。移动的最小步数为 $r-\mathit{\text{startPos}}$；
2. 如果 $\mathit{\text{startPos}}\ge r$，那么就是从 $\mathit{\text{startPos}}$ 一直向左移动到 $l$。移动的最小步数为 $\mathit{\text{startPos}}-l$；
3. 如果 $l<\mathit{\text{startPos}}<r$，那么可以从 $\mathit{\text{startPos}}$ 向左移动到 $l$，再向右移动到 $r$；也可以从 $\mathit{\text{startPos}}$ 向右移动到 $r$，再向左移动到 $l$。移动的最小步数为 $r-l+min(|\mathit{\text{startPos}}-l|,|r-\mathit{\text{startPos}}|)$。

以上三种情况可以统一用式子 $r-l+min(|\mathit{\text{startPos}}-l|,|r-\mathit{\text{startPos}}|)$ 表示。

假设我们固定区间右端点 $r$，向右移动左端点 $l$，我们来看看最小移动步数是怎么变化的。

1. 如果 $\mathit{\text{startPos}}\le l$，随着 $l$ 的增大，最小步数不会发生变化。
2. 如果 $\mathit{\text{startPos}}>l$，随着 $l$ 的增大，最小步数会减小。

因此，随着 $l$ 的增大，最小移动步数一定是非严格单调递减的。基于此，我们可以使用双指针的方法，找出所有符合条件的最大区间，然后取所有符合条件的区间中水果总数最大的一个作为答案。

具体地，我们用两个指针 $i$ 和 $j$ 分别指向区间的左右下标，初始时 $i=j=0$。另外用一个变量 $s$ 记录区间内的水果总数，初始时 $s=0$。

每次我们将 $j$ 加入区间中，然后更新 $s=s+\mathit{\text{fruits}}[j][1]$。如果此时区间内的最小步数 $\mathit{\text{fruits}}[j][0]-\mathit{\text{fruits}}[i][0]+min(|\mathit{\text{startPos}}-\mathit{\text{fruits}}[i][0]|,|\mathit{\text{startPos}}-\mathit{\text{fruits}}[j][0]|)$ 大于 $k$，那么我们就将 $i$ 循环向右移动，直到 $i>j$ 或者区间内的最小步数小于等于 $k$。此时我们更新答案 $\mathit{\text{ans}}=max(\mathit{\text{ans}},s)$。继续移动 $j$，直到 $j$ 到达数组末尾。

最后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func maxTotalFruits(fruits [][]int, startPos int, k int) (ans int) {
	var s, i int
	for j, f := range fruits {
		s += f[1]
		for i <= j && f[0]-fruits[i][0]+min(abs(startPos-fruits[i][0]), abs(startPos-f[0])) > k {
			s -= fruits[i][1]
			i += 1
		}
		ans = max(ans, s)
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

2111. 使数组 K 递增的最少操作次数

困难1 种解法

标签：数组、二分查找、最长上升子序列

题目、示例与约束

给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。

如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。

• 比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为：
  • arr[0] <= arr[2] (4 <= 5)
  • arr[1] <= arr[3] (1 <= 2)
  • arr[2] <= arr[4] (5 <= 6)
  • arr[3] <= arr[5] (2 <= 2)
• 但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]），对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。

每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。

请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。

 

示例 1：

输入：arr = [5,4,3,2,1], k = 1
输出：4
解释：
对于 k = 1 ，数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ，因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。

示例 2：

输入：arr = [4,1,5,2,6,2], k = 2
输出：0
解释：
这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ，有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的，我们不需要进行任何操作。

示例 3：

输入：arr = [4,1,5,2,6,2], k = 3
输出：2
解释：
下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。

 

提示：

• 1 <= arr.length <= 105
• 1 <= arr[i], k <= arr.length

方法一 · Go 实现

思考

$k$-递增只约束下标模 $k$ 相同的子序列，这 $k$ 组互不影响，操作数之和即为答案。对一组而言，一次操作可改任意元素，最少修改次数等于长度减去最长非递减子序列长度。

$n\le {10}^5$，对每组求 LDS 若用 $O(L^2)$ 动态规划会超时。非递减允许相等，可用 $\mathtt{\text{bisect\_right}}$ 维护堆叠数组，在 $O(L\log L)$ 内得到最长非递减长度。

为此对 $i=0,\dots ,k-1$ 分别处理 $\mathit{\text{arr}}[i::k]$，将「组长度减去 LIS 长度」求和。

func kIncreasing(arr []int, k int) int {
	searchRight := func(arr []int, x int) int {
		left, right := 0, len(arr)
		for left < right {
			mid := (left + right) >> 1
			if arr[mid] > x {
				right = mid
			} else {
				left = mid + 1
			}
		}
		return left
	}

	lis := func(arr []int) int {
		var t []int
		for _, x := range arr {
			idx := searchRight(t, x)
			if idx == len(t) {
				t = append(t, x)
			} else {
				t[idx] = x
			}
		}
		return len(arr) - len(t)
	}

	n := len(arr)
	ans := 0
	for i := 0; i < k; i++ {
		var t []int
		for j := i; j < n; j += k {
			t = append(t, arr[j])
		}
		ans += lis(t)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2137. 通过倒水操作让所有的水桶所含水量相等 🔒

中等1 种解法

标签：数组、二分查找

题目、示例与约束

你有 n 个水桶，每个水桶中所含的水量用一个 下标从 0 开始 的数组 buckets 给出，第 i 个水桶中有 buckets[i] 升水。

你想让所有的水桶中所含的水量相同。你可以从一个水桶向其它任意一个水桶倒任意数量的水（可以不是整数）。但是，你每倒 k 升水，百分之 loss 的水会洒掉。

请返回经过倒水操作，所有水桶中的水量相同时，每个水桶中的 最大 水量。如果你的答案和标准答案的误差不超过 10-5，那么答案将被通过。

 

示例 1:

输入: buckets = [1,2,7], loss = 80
输出: 2.00000
解释: 从水桶 2 向水桶 0 倒 5 升水。
5 * 80% = 4 升水会洒掉，水桶 0 只会获得 5 - 4 = 1 升水。
此时所有的水桶中都含有 2 升水，所以返回 2。

示例 2:

输入: buckets = [2,4,6], loss = 50
输出: 3.50000
解释: 从水桶 1 向水桶 0 倒 0.5 升水。
0.5 * 50% = 0.25 升水会洒掉，水桶 0 只会获得 0.5 - 0.25 = 0.25 升水。
此时, buckets = [2.25, 3.5, 6].

从水桶 2 向水桶 0 倒 2.5 升水。
2.5 * 50% = 1.25 升水会洒掉，水桶 0 只会获得 2.5 - 1.25 = 1.25 升水。
此时所有的水桶中都含有 3.5 升水，所以返回 3.5。

示例 3:

输入: buckets = [3,3,3,3], loss = 40
输出: 3.00000
解释: 所有的水桶已经含有相同的水量。

 

提示:

• 1 <= buckets.length <= 105
• 0 <= buckets[i] <= 105
• 0 <= loss <= 99

方法一：二分查找（浮点数二分） · Go 实现

思考

倒水有损耗，最终公共水位越高越难达到，具有单调性。水位是实数，无法枚举。直接模拟多次倾倒也难以控制精度。

对候选水位 $v$，多出的水汇总为 $a$，不足的一侧需计入损耗后的需求 $b$；若 $a\ge b$ 则可达到 $v$。在 $[0,max\mathit{\text{buckets}}]$ 上对浮点二分。

$\mathtt{\text{check}}$ 扫描全部桶，二分直到区间宽度小于 ${10}^{-5}$。

我们注意到，如果一个水量 $x$ 满足条件，那么所有小于 $x$ 的水量也满足条件。因此我们可以使用二分查找的方法找到最大的满足条件的水量。

我们定义二分查找的左边界 $l=0$，右边界 $r=max(buckets)$。每次二分查找时，我们取 $l$ 和 $r$ 的中点 $mid$，判断 $mid$ 是否满足条件。如果满足条件，那么我们将 $l$ 更新为 $mid$，否则我们将 $r$ 更新为 $m$。在二分查找结束后，最大的满足条件的水量即为 $l$。

问题的关键转换为如果判断一个水量 $v$ 是否满足条件。我们可以遍历所有水桶，对于每个水桶，如果其水量大于 $v$，那么需要倒出 $x-v$ 的水量；如果其水量小于 $v$，那么需要向其中倒入 $(v-x)\times \frac{100}{100-\mathit{\text{loss}}}$ 的水量。如果倒出的水量大于等于倒入的水量，那么说明 $v$ 满足条件。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别是数组 $buckets$ 的长度和最大值。二分查找的时间复杂度为 $O(\log M)$，每次二分查找需要遍历数组 $buckets$，时间复杂度为 $O(n)$。空间复杂度 $O(1)$。

func equalizeWater(buckets []int, loss int) float64 {
	check := func(v float64) bool {
		var a, b float64
		for _, x := range buckets {
			if float64(x) >= v {
				a += float64(x) - v
			} else {
				b += (v - float64(x)) * 100 / float64(100-loss)
			}
		}
		return a >= b
	}

	l, r := float64(0), float64(slices.Max(buckets))
	for r-l > 1e-5 {
		mid := (l + r) / 2
		if check(mid) {
			l = mid
		} else {
			r = mid
		}
	}
	return l
}

力扣原题 · Doocs 题解来源

2187. 完成旅途的最少时间

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个数组 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 <= 105
• 1 <= time[i], totalTrips <= 107

方法一：二分查找 · Go 实现

思考

时刻 $t$ 内完成的旅途数为 $\sum \lfloor t/{\mathit{\text{time}}}_i\rfloor$，该函数对 $t$ 单调，求最小的 $t$ 使得其不小于 $\mathit{\text{totalTrips}}$。枚举 $t$ 的上界可达 $min(\mathit{\text{time}})\times \mathit{\text{totalTrips}}$，线性扫描不可行。

在 $[0,\mathit{\text{mx}})$ 上对「完成趟数」做二分，库函数 $\mathtt{\text{bisect\_left}}$ 即找到最小可行时刻。

每次判定为对数组的一次线性求和。

我们注意到，如果我们能在 $t$ 时间内至少完成 $totalTrips$ 趟旅途，那么在 $t^{\prime }>t$ 时间内也能至少完成 $totalTrips$ 趟旅途。因此我们可以使用二分查找的方法来找到最小的 $t$。

我们定义二分查找的左边界 $l=1$，右边界 $r=min(time)\times \mathit{\text{totalTrips}}$。每一次二分查找，我们计算中间值 $\mathit{\text{mid}}=\frac{l+r}{2}$，然后计算在 $\mathit{\text{mid}}$ 时间内能完成的旅途数目。如果这个数目大于等于 $\mathit{\text{totalTrips}}$，那么我们将右边界缩小到 $\mathit{\text{mid}}$，否则我们将左边界扩大到 $\mathit{\text{mid}}+1$。

最后返回左边界即可。

时间复杂度 $O(n\times \log (m\times k))$，其中 $n$ 和 $k$ 分别是数组 $time$ 的长度和 $totalTrips$，而 $m$ 是数组 $time$ 中的最小值。空间复杂度 $O(1)$。

func minimumTime(time []int, totalTrips int) int64 {
	mx := slices.Min(time) * totalTrips
	return int64(sort.Search(mx, func(x int) bool {
		cnt := 0
		for _, v := range time {
			cnt += x / v
		}
		return cnt >= totalTrips
	}))
}

力扣原题 · Doocs 题解来源

2223. 构造字符串的总得分和

困难1 种解法

标签：字符串、二分查找、字符串匹配、后缀数组、哈希函数、滚动哈希、KMP 算法、扩展 KMP

题目、示例与约束

你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 si 。

• 比方说，s = "abaca" ，s1 == "a" ，s2 == "ca" ，s3 == "aca" 依次类推。

si 的 得分 为 si 和 sn 的 最长公共前缀 的长度（注意 s == sn ）。

给你最终的字符串 s ，请你返回每一个 si 的 得分之和 。

 

示例 1：

输入：s = "babab"
输出：9
解释：
s1 == "b" ，最长公共前缀是 "b" ，得分为 1 。
s2 == "ab" ，没有公共前缀，得分为 0 。
s3 == "bab" ，最长公共前缀为 "bab" ，得分为 3 。
s4 == "abab" ，没有公共前缀，得分为 0 。
s5 == "babab" ，最长公共前缀为 "babab" ，得分为 5 。
得分和为 1 + 0 + 3 + 0 + 5 = 9 ，所以我们返回 9 。

示例 2 ：

输入：s = "azbazbzaz"
输出：14
解释：
s2 == "az" ，最长公共前缀为 "az" ，得分为 2 。
s6 == "azbzaz" ，最长公共前缀为 "azb" ，得分为 3 。
s9 == "azbazbzaz" ，最长公共前缀为 "azbazbzaz" ，得分为 9 。
其他 si 得分均为 0 。
得分和为 2 + 3 + 9 = 14 ，所以我们返回 14 。

 

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母。

方法一 · Go 实现

思考

每个前缀添加过程得到的 $s_i$ 其实是 $s$ 的长度为 $i$ 的后缀，其得分是该后缀与 $s$ 本身的最长公共前缀。对每个后缀暴力比较是 $O(n^2)$， $n\le {10}^5$ 不可接受。

这些 LCP 正是 Z 函数： $z[i]$ 表示 $s[i:]$ 与 $s$ 的最长公共前缀，再补上 $z[0]=n$。线性求出 Z 数组后求和即可。若用字符串哈希，也可对每个起点二分 LCP，时间 $O(n\log n)$。

对字符串 $s$ 求 Z 函数， $z[i]$ 为 $s[i:]$ 与 $s$ 的最长公共前缀长度。长度为 $i$ 的后缀 $s_i$ 的得分即 $z[n-i]$，整串得分则为 $n$。因此将 Z 数组求和并加上 $n$ 即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

func sumScores(s string) int64 {
	n := len(s)
	z := make([]int, n)
	for i, l, r := 1, 0, 0; i < n; i++ {
		if i <= r {
			z[i] = min(r-i+1, z[i-l])
		}
		for i+z[i] < n && s[z[i]] == s[i+z[i]] {
			z[i]++
		}
		if i+z[i]-1 > r {
			l, r = i, i+z[i]-1
		}
	}
	ans := int64(n)
	for _, x := range z {
		ans += int64(x)
	}
	return ans
}

力扣原题 · Doocs 题解来源