LeetCode Go · 贪心（8）

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

来源与许可

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

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

2358. 分组的最大数量

中等1 种解法

标签：贪心、数组、数学、二分查找

题目、示例与约束

给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：

• 第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
• 第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。

返回可以形成的 最大 组数。

 

示例 1：

输入：grades = [10,6,12,7,3,5]
输出：3
解释：下面是形成 3 个分组的一种可行方法：
- 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1
- 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2
- 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3 
可以证明无法形成超过 3 个分组。

示例 2：

输入：grades = [8,8]
输出：1
解释：只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。

 

提示：

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

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

思考

组的人数须严格递增，分数和也须严格递增。 $n\le {10}^5$，不能搜索分组。将成绩排序后依次分配 $1,2,\dots ,k$ 人，分数和自动递增。

人数约束成为 $\frac{k(k+1)}{2}\le n$。对 $k$ 二分（实现上对 $x^2+x$ 相对 $2n$ 做 $bisect$）得到最大可行组数。

我们观察题目中的条件，第 $i$ 组的学生人数要小于第 $i+1$ 组的学生人数，且第 $i$ 组的学生总成绩要小于第 $i+1$ 组的学生总成绩，我们只需要将学生按照成绩从小到大排序，然后每一组依次分配 $1$, $2$, ..., $k$ 个学生即可。如果最后一组的学生人数不足 $k$ 个，那么我们可以将这些学生分配到前面的最后一组中。

因此，我们要找到最大的 $k$，使得 $\frac{(1+k)\times k}{2}\le n$，其中 $n$ 为学生的总人数。我们可以使用二分查找来求解。

我们定义二分查找的左边界为 $l=1$，右边界为 $r=n$，每一次二分查找的中点为 $mid=\lfloor \frac{l+r+1}{2}\rfloor$，如果 $(1+mid)\times mid>2\times n$，则说明 $mid$ 太大，我们需要将右边界缩小至 $mid-1$，否则我们需要将左边界增大至 $mid$。

最后，我们将 $l$ 作为答案返回即可。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为学生的总人数。

func maximumGroups(grades []int) int {
	n := len(grades)
	return sort.Search(n, func(k int) bool {
		k++
		return k*k+k > n*2
	})
}

力扣原题 · Doocs 题解来源

2366. 将数组排序的最少替换次数

困难1 种解法

标签：贪心、数组、数学

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。每次操作中，你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。

• 比方说，nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [5,2,4,7] 。

请你执行上述操作，将数组变成元素按 非递减 顺序排列的数组，并返回所需的最少操作次数。

 

示例 1：

输入：nums = [3,9,3]
输出：2
解释：以下是将数组变成非递减顺序的步骤：
- [3,9,3] ，将9 变成 3 和 6 ，得到数组 [3,3,6,3] 
- [3,3,6,3] ，将 6 变成 3 和 3 ，得到数组 [3,3,3,3,3] 
总共需要 2 步将数组变成非递减有序，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：数组已经是非递减顺序，所以我们返回 0 。

 

提示：

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

方法一：贪心 · Go 实现

思考

把一个数拆成若干正整数之和，目标是最终非递减，且拆分次数最少。 $n\le {10}^5$，须从右往左确定上界。

右侧已确定的最大值 $mx$ 不应再被拆小。若 $nums[i]\le mx$ 则更新 $mx$；否则拆成 $k=\lceil nums[i]/mx\rceil$ 段，次数加 $k-1$，并把新的上界改成 $\lfloor nums[i]/k\rfloor$，以便左侧仍尽量大。

我们观察发现，要使得数组 $nums$ 变成非递减有序，也即单调递增，那么数组后面的元素应该尽可能大，所以，将数组 $nums$ 的最后一个元素 $nums[n-1]$ 替换成多个更小的数是没有必要的。

也即是说，我们可以从后往前遍历数组 $nums$，并且维护当前的最大值 $mx$，初始时 $mx=nums[n-1]$。

• 若当前遍历到的元素 $nums[i]\le mx$，此时不需要将 $nums[i]$ 进行替换，我们直接更新 $mx=nums[i]$ 即可。
• 否则，我们需要将 $nums[i]$ 替换成多个和为 $nums[i]$ 的数，这些数的最大值为 $mx$，总共替换成 $k=\lceil \frac{nums[i]}{mx}\rceil$ 个数，所以需要进行 $k-1$ 次操作，累加到答案中。这 $k$ 个数中，最小的数为 $\lfloor \frac{nums[i]}{k}\rfloor$，因此，我们更新 $mx=\lfloor \frac{nums[i]}{k}\rfloor$。

遍历结束，返回总的操作次数即可。

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

func minimumReplacement(nums []int) (ans int64) {
	n := len(nums)
	mx := nums[n-1]
	for i := n - 2; i >= 0; i-- {
		if nums[i] <= mx {
			mx = nums[i]
			continue
		}
		k := (nums[i] + mx - 1) / mx
		ans += int64(k - 1)
		mx = nums[i] / k
	}
	return
}

力扣原题 · Doocs 题解来源

2383. 赢得比赛需要的最少训练时长

简单1 种解法

标签：贪心、数组

题目、示例与约束

你正在参加一场比赛，给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都 严格 超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验 增加 experience[i]，但会将你的精力 减少  energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者 将精力增加 1 。

返回击败全部 n 个对手需要训练的 最少 小时数目。

 

示例 1：

输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出：8
解释：在 6 小时训练后，你可以将精力提高到 11 ，并且再训练 2 个小时将经验提高到 5 。
按以下顺序与对手比赛：
- 你的精力与经验都超过第 0 个对手，所以获胜。
  精力变为：11 - 1 = 10 ，经验变为：5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手，所以获胜。
  精力变为：10 - 4 = 6 ，经验变为：7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手，所以获胜。
  精力变为：6 - 3 = 3 ，经验变为：13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手，所以获胜。
  精力变为：3 - 2 = 1 ，经验变为：16 + 1 = 17 。
在比赛前进行了 8 小时训练，所以返回 8 。
可以证明不存在更小的答案。

示例 2：

输入：initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
输出：0
解释：你不需要额外的精力和经验就可以赢得比赛，所以返回 0 。

 

提示：

• n == energy.length == experience.length
• 1 <= n <= 100
• 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

方法一：贪心 + 模拟 · Go 实现

思考

必须按顺序击败对手，开战时精力与经验都要严格更大。 $n\le 100$，按序模拟并在不足时立刻补齐。

精力不够则训练到对手精力加一，经验同理；战后精力减少、经验增加。各场不足量之和即最少训练时数。

我们不妨记当前的精力为 $x$，经验为 $y$。

接下来，我们遍历每个对手，对于第 $i$ 个对手，记其精力为 $dx$，经验为 $dy$。

• 如果 $x\le dx$，那么我们需要训练 $dx+1-x$ 小时，将精力提升到 $dx+1$；
• 如果 $y\le dy$，那么我们需要训练 $dy+1-y$ 小时，将经验提升到 $dy+1$；
• 然后我们将精力减去 $dx$，经验加上 $dy$。

最后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 为对手的数量。空间复杂度 $O(1)$。

func minNumberOfHours(x int, y int, energy []int, experience []int) (ans int) {
	for i, dx := range energy {
		dy := experience[i]
		if x <= dx {
			ans += dx + 1 - x
			x = dx + 1
		}
		if y <= dy {
			ans += dy + 1 - y
			y = dy + 1
		}
		x -= dx
		y += dy
	}
	return
}

力扣原题 · Doocs 题解来源

2384. 最大回文数字

中等1 种解法

标签：贪心、哈希表、字符串、计数

题目、示例与约束

给你一个仅由数字（0 - 9）组成的字符串 num 。

请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。

注意：

• 你 无需 使用 num 中的所有数字，但你必须使用 至少 一个数字。
• 数字可以重新排序。

 

示例 1：

输入：num = "444947137"
输出："7449447"
解释：
从 "444947137" 中选用数字 "4449477"，可以形成回文整数 "7449447" 。
可以证明 "7449447" 是能够形成的最大回文整数。

示例 2：

输入：num = "00009"
输出："9"
解释：
可以证明 "9" 能够形成的最大回文整数。
注意返回的整数不应含前导零。

 

提示：

• 1 <= num.length <= 105
• num 由数字（0 - 9）组成

方法一：统计 + 贪心 · Go 实现

思考

用给定数字重排成最大回文，可丢弃部分数字。 $n\le {10}^5$，应按数位贪心而非搜索排列。

统计频次后，最大的奇数次数字做中心并留偶数次。再从 $0$ 到 $9$ 把一半贴到两侧。去掉两端的 $0$；若空则答案为 $0$。

用 $cnt$ 数组记录每个数字出现的次数。

回文数字需要满足回文串中最多有一个数字出现了奇数次，因此我们先找最大的、出现了奇数次的数字 $v$（也可能不存在），作为回文数字的中间数字，对应的 $cnt$ 减 $1$。

接下来我们从回文数字中间，按数字从小到大的顺序，往左右两边扩散（也可以枚举回文串的右半部分，然后将右半部分反转，得到左半部分）。这样我们可以得到一个“可能”含有前导零的回文串。

我们去除回文串的前导零，若回文串为空，则返回“0”。否则返回该回文串。

时间复杂度 $O(n)$，其中 $n$ 为 $num$ 的长度。

func largestPalindromic(num string) string {
	cnt := make([]int, 10)
	for _, c := range num {
		cnt[c-'0']++
	}
	ans := ""
	for i := 9; i >= 0; i-- {
		if cnt[i]%2 == 1 {
			ans = strconv.Itoa(i)
			cnt[i]--
			break
		}
	}
	for i := 0; i < 10; i++ {
		if cnt[i] > 0 {
			cnt[i] >>= 1
			s := strings.Repeat(strconv.Itoa(i), cnt[i])
			ans = s + ans + s
		}
	}
	ans = strings.Trim(ans, "0")
	if ans == "" {
		return "0"
	}
	return ans
}

力扣原题 · Doocs 题解来源

2389. 和有限的最长子序列

简单2 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

 

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

 

提示：

• n == nums.length
• m == queries.length
• 1 <= n, m <= 1000
• 1 <= nums[i], queries[i] <= 106

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

思考

子序列和不超过查询值且尽量长，应取最小的若干元素。 $n,m\le 1000$，排序后前缀和即可。

升序后前缀 $s[j]$ 是选 $j+1$ 个最小元的和。对每个查询二分第一个超过上限的位置，下标即最大长度。

根据题目描述，对于每个 $\mathit{\text{queries[i]}}$，我们需要找到一个子序列，使得该子序列的元素和不超过 $\mathit{\text{queries[i]}}$，且该子序列的长度最大化。显然，我们应该选择尽可能小的元素，这样才能使得子序列的长度最大化。

因此，我们可以先将数组 $\mathit{\text{nums}}$ 进行升序排序，然后对于每个 $\mathit{\text{queries[i]}}$，我们可以使用二分查找，找到最小的下标 $j$，使得 $\mathit{\text{nums}}[0]+\mathit{\text{nums}}[1]+\cdots +\mathit{\text{nums}}[j]>\mathit{\text{queries[i]}}$。此时 $\mathit{\text{nums}}[0]+\mathit{\text{nums}}[1]+\cdots +\mathit{\text{nums}}[j-1]$ 就是满足条件的子序列的元素和，且该子序列的长度为 $j$。因此，我们可以将 $j$ 加入答案数组中。

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

func answerQueries(nums []int, queries []int) (ans []int) {
	sort.Ints(nums)
	for i := 1; i < len(nums); i++ {
		nums[i] += nums[i-1]
	}
	for _, q := range queries {
		ans = append(ans, sort.SearchInts(nums, q+1))
	}
	return
}

方法二：排序 + 离线查询 + 双指针 · Go 实现

思考

方法一对每个查询独立二分。查询离线按上限排序后，双指针只向前加元素，总时间在排序之外变为线性。

与方法一类似，我们可以先对数组 $nums$ 进行升序排列。

接下来，我们定义一个长度与 $queries$ 相同的下标数组 $idx$，其中 $idx[i]=i$，然后我们对数组 $idx$ 按照 $queries$ 中的元素值进行升序排序。这样，我们就可以按照 $queries$ 中的元素值从小到大的顺序进行处理。

我们使用一个变量 $s$ 记录当前已经选择的元素的和，使用一个变量 $j$ 记录当前已经选择的元素的个数。初始时 $s=j=0$。

我们遍历下标数组 $idx$，对于其中的每个下标 $i$，我们循环地将数组 $nums$ 中的元素加入到当前的子序列中，直到 $s+nums[j]>queries[i]$，此时 $j$ 即为满足条件的子序列的长度，我们将 $ans[i]$ 的值设为 $j$，然后继续处理下一个下标。

遍历完下标数组 $idx$ 后，我们即可得到答案数组 $ans$，其中 $ans[i]$ 即为满足 $queries[i]$ 的子序列的长度。

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

func answerQueries(nums []int, queries []int) (ans []int) {
	sort.Ints(nums)
	m := 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)
	s, j := 0, 0
	for _, i := range idx {
		for j < len(nums) && s+nums[j] <= queries[i] {
			s += nums[j]
			j++
		}
		ans[i] = j
	}
	return
}

力扣原题 · Doocs 题解来源

2405. 子字符串的最优划分

中等1 种解法

标签：贪心、哈希表、字符串

题目、示例与约束

给你一个字符串 s ，请你将该字符串划分成一个或多个 子字符串 ，并满足每个子字符串中的字符都是 唯一 的。也就是说，在单个子字符串中，字母的出现次数都不超过 一次 。

满足题目要求的情况下，返回 最少 需要划分多少个子字符串。

注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。

 

示例 1：

输入：s = "abacaba"
输出：4
解释：
两种可行的划分方法分别是 ("a","ba","cab","a") 和 ("ab","a","ca","ba") 。
可以证明最少需要划分 4 个子字符串。

示例 2：

输入：s = "ssssss"
输出：6
解释：
只存在一种可行的划分方法 ("s","s","s","s","s","s") 。

 

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成

方法一：贪心 · Go 实现

思考

划分方案随段数指数增长， $n\le {10}^5$ 无法枚举。题目要求每段字符互异且份数最少，等价于每段尽量长：当前段再纳入某字符会重复时才切开。

小写字母仅 $26$ 个，用一个整数 $\mathit{\text{mask}}$ 的各位记录本段已出现字母。遇冲突则份数加一并清空 $\mathit{\text{mask}}$，再纳入当前字符。一遍扫描即可。

根据题意，每个子字符串应该尽可能长，且包含的字符唯一，因此，我们只需要贪心地进行划分即可。

我们定义一个二进制整数 $\mathit{\text{mask}}$ 来记录当前子字符串中出现的字符，其中 $\mathit{\text{mask}}$ 的第 $i$ 位为 $1$ 表示第 $i$ 个字母已经出现过，为 $0$ 表示未出现过。另外，我们还需要一个变量 $\mathit{\text{ans}}$ 来记录划分的子字符串个数，初始时 $\mathit{\text{ans}}=1$。

遍历字符串 $s$ 中的每个字符，对于每个字符 $c$，我们将其转换为 $0$ 到 $25$ 之间的整数 $x$，然后判断 $\mathit{\text{mask}}$ 的第 $x$ 位是否为 $1$，如果为 $1$，说明当前字符 $c$ 与当前子字符串中的字符有重复，此时 $\mathit{\text{ans}}$ 需要加 $1$，并将 $\mathit{\text{mask}}$ 置为 $0$；否则，将 $\mathit{\text{mask}}$ 的第 $x$ 位置为 $1$。然后，我们将 $\mathit{\text{mask}}$ 更新为 $\mathit{\text{mask}}$ 与 $2^x$ 的按位或结果。

最后，返回 $\mathit{\text{ans}}$ 即可。

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

func partitionString(s string) int {
	ans, mask := 1, 0
	for _, c := range s {
		x := int(c - 'a')
		if mask>>x&1 == 1 {
			ans++
			mask = 0
		}
		mask |= 1 << x
	}
	return ans
}

力扣原题 · Doocs 题解来源

2406. 将区间分为最少组数

中等1 种解法

标签：贪心、数组、双指针、前缀和、排序、堆（优先队列）

题目、示例与约束

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

 

示例 1：

输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：
- 第 1 组：[1, 5] ，[6, 8] 。
- 第 2 组：[2, 3] ，[5, 10] 。
- 第 3 组：[1, 10] 。
可以证明无法将区间划分为少于 3 个组。

示例 2：

输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
输出：1
解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。

 

提示：

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 106

方法一：贪心 + 优先队列（小根堆） · Go 实现

思考

$n\le {10}^5$，若对每个区间扫描已有组，最坏平方级。一组内区间不能相交，故组数等于同一时刻重叠数的最大值。按左端排序后，一个区间能加入某组当且仅当该组当前最右端点小于其左端。

用小根堆维护各组右端：能接到堆顶则弹出再压入新右端，否则新开一组。堆的大小即为最少组数。

我们先将区间按左端点排序，用小根堆维护每组的最右端点（堆顶是所有组的最右端点的最小值）。

接下来，我们遍历每个区间：

• 若当前区间左端点大于堆顶元素，说明当前区间可以加入到堆顶元素所在的组中，我们直接弹出堆顶元素，然后将当前区间的右端点放入堆中；
• 否则，说明当前没有组能容纳当前区间，那么我们就新建一个组，将当前区间的右端点放入堆中。

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

func minGroups(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	q := hp{}
	for _, e := range intervals {
		if q.Len() > 0 && q.IntSlice[0] < e[0] {
			heap.Pop(&q)
		}
		heap.Push(&q, e[1])
	}
	return q.Len()
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

力扣原题 · Doocs 题解来源

2410. 运动员和训练师的最大匹配数

中等2 种解法

标签：贪心、数组、双指针、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

 

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

 

提示：

• 1 <= players.length, trainers.length <= 105
• 1 <= players[i], trainers[j] <= 109

方法一：贪心 + 双指针 · Go 实现

思考

$n,m\le {10}^5$，两两尝试配对会超时。训练师若能匹配更弱的运动员，也就能匹配更强的运动员，所以应把刚好够用的训练师分给当前最弱的运动员。

两边按能力升序排列后，从弱到强处理运动员，训练师指针只向前走：能力不足的跳过，遇到第一个够用的就配上一对。总时间由排序决定。

把运动员和训练师都按能力从小到大排序。指针 $i$ 和 $j$ 分别指向当前考虑到的运动员和训练师。

从最弱的运动员开始匹配。训练师能力低于这名运动员时，将 $j$ 右移，直到能力足够，或训练师已经用完。训练师用完后，后面的运动员只会更强，匹配结束，答案就是已经配上的人数 $i$。否则当前这一对可以匹配，两个指针各前进一步。所有运动员都匹配成功时，返回运动员人数。

时间复杂度 $O(m\times \log m+n\times \log n)$，空间复杂度 $O(max(\log m,\log n))$。其中 $m$ 和 $n$ 分别为运动员和训练师的数量。

func matchPlayersAndTrainers(players []int, trainers []int) int {
	sort.Ints(players)
	sort.Ints(trainers)
	m, n := len(players), len(trainers)
	for i, j := 0, 0; i < m; i, j = i+1, j+1 {
		for j < n && trainers[j] < players[i] {
			j++
		}
		if j == n {
			return i
		}
	}
	return m
}

方法二：贪心 + 双指针（遍历训练师） · Go 实现

思考

方法一在处理每名运动员时，还要用内层循环跳过能力不足的训练师，训练师用完则提前返回。改成遍历训练师之后，这两步都可以省去。

两边按能力升序排列，从弱到强查看训练师，指针停在最弱的未匹配运动员上。训练师能力不足时，剩余运动员只会更强，直接跳过。能力足够就完成匹配，指针前进一步。指针最终的位置就是匹配数，复杂度与方法一相同。

同样先把运动员和训练师按能力从小到大排序。指针 $j$ 指向尚未匹配的最弱运动员，初始为 $0$。

从弱到强查看每名训练师。若仍有运动员未匹配，且该运动员的能力不超过这名训练师，就配成一对，并将 $j$ 加一。否则这名训练师无法匹配剩下的任何运动员，直接跳过。遍历结束后， $j$ 就是最大匹配数。

时间复杂度 $O(m\times \log m+n\times \log n)$，空间复杂度 $O(max(\log m,\log n))$。其中 $m$ 和 $n$ 分别为运动员和训练师的数量。

func matchPlayersAndTrainers(players []int, trainers []int) int {
	sort.Ints(players)
	sort.Ints(trainers)
	j, m := 0, len(players)
	for _, t := range trainers {
		if j < m && players[j] <= t {
			j++
		}
	}
	return j
}

力扣原题 · Doocs 题解来源

2412. 完成所有交易的初始最少钱数

困难1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 transactions，其中transactions[i] = [costi, cashbacki] 。

数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻，你有一定数目的钱 money ，为了完成交易 i ，money >= costi 这个条件必须为真。执行交易后，你的钱数 money 变成 money - costi + cashbacki 。

请你返回 任意一种 交易顺序下，你都能完成所有交易的最少钱数 money 是多少。

 

示例 1：

输入：transactions = [[2,1],[5,0],[4,2]]
输出：10
解释：
刚开始 money = 10 ，交易可以以任意顺序进行。
可以证明如果 money < 10 ，那么某些交易无法进行。

示例 2：

输入：transactions = [[3,0],[0,3]]
输出：3
解释：
- 如果交易执行的顺序是 [[3,0],[0,3]] ，完成所有交易需要的最少钱数是 3 。
- 如果交易执行的顺序是 [[0,3],[3,0]] ，完成所有交易需要的最少钱数是 0 。
所以，刚开始钱数为 3 ，任意顺序下交易都可以全部完成。

 

提示：

• 1 <= transactions.length <= 105
• transactions[i].length == 2
• 0 <= costi, cashbacki <= 109

方法一：贪心 · Go 实现

思考

$n\le {10}^5$，枚举交易顺序不可行。亏钱交易的净亏损必须发生，总和 $s$ 固定；钱最少的时刻出现在某笔交易扣款之后、回款之前。

把每一笔轮流当作「现金最低点所在的那笔」：若该笔亏钱，此前已计入的亏损含 $a-b$，再加上本笔支出 $a$，即需 $s+b$；若该笔赚钱，此前仍需备齐全部亏损 $s$ 再支付 $a$。取所有情况的最大值。

我们先累计所有负收益，记为 $s$。然后枚举每个交易 $\text{transactions}[i]=[a,b]$ 作为最后一个交易，如果 $a>b$，说明当前的交易是亏钱的，而这个交易在此前我们累计负收益的时候，已经被计算，因此取 $s+b$ 更新答案；否则，取 $s+a$ 更新答案。

时间复杂度 $O(n)$，其中 $n$ 为交易数。空间复杂度 $O(1)$。

func minimumMoney(transactions [][]int) int64 {
	s, ans := 0, 0
	for _, e := range transactions {
		s += max(0, e[0]-e[1])
	}
	for _, e := range transactions {
		if e[0] > e[1] {
			ans = max(ans, s+e[1])
		} else {
			ans = max(ans, s+e[0])
		}
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2422. 使用合并操作将数组转换为回文序列 🔒

中等1 种解法

标签：贪心、数组、双指针

题目、示例与约束

给定一个由 正整数 组成的数组 nums。

可以对阵列执行如下操作，次数不限:

• 选择任意两个 相邻 的元素并用它们的 和 替换 它们。
  • 例如，如果 nums = [1,2,3,1]，则可以应用一个操作使其变为 [1,5,1]。

返回将数组转换为 回文序列 所需的 最小 操作数。

 

示例 1:

输入: nums = [4,3,2,1,2,3,1]
输出: 2
解释: 我们可以通过以下 2 个操作将数组转换为回文:
- 在数组的第 4 和第 5 个元素上应用该操作，nums 将等于 [4,3,2,3,3,1].
- 在数组的第 5 和第 6 个元素上应用该操作，nums 将等于 [4,3,2,3,4].
数组 [4,3,2,3,4] 是一个回文序列。
可以证明，2 是所需的最小操作数。

示例 2:

输入: nums = [1,2,3,4]
输出: 3
解释: 我们在任意位置进行 3 次运算，最后得到数组 [10]，它是一个回文序列。

 

提示:

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

方法一：贪心 + 双指针 · Go 实现

思考

合并只能把相邻数相加，目标是回文，操作次数应尽量少。两端最终必须相等，因此应从外向内配对：当前左右和谁更小，就在较小一侧继续合并。

双指针维护左右累计和 $a$、 $b$：较小一侧并入下一个元素并计数，相等则同时内收。每个元素至多被并入一次，线性完成。

定义两个指针 $i$ 和 $j$，分别指向数组的首尾，用变量 $a$ 和 $b$ 分别表示首尾两个元素的值，变量 $ans$ 表示操作次数。

如果 $a<b$，我们将指针 $i$ 向右移动一位，即 $i\leftarrow i+1$，然后将 $a$ 加上指针 $i$ 指向的元素的值，即 $a\leftarrow a+nums[i]$，同时将操作次数加一，即 $ans\leftarrow ans+1$。

如果 $a>b$，我们将指针 $j$ 向左移动一位，即 $j\leftarrow j-1$，然后将 $b$ 加上指针 $j$ 指向的元素的值，即 $b\leftarrow b+nums[j]$，同时将操作次数加一，即 $ans\leftarrow ans+1$。

否则，说明 $a=b$，此时我们将指针 $i$ 向右移动一位，即 $i\leftarrow i+1$，将指针 $j$ 向左移动一位，即 $j\leftarrow j-1$，并且更新 $a$ 和 $b$ 的值，即 $a\leftarrow nums[i]$ 以及 $b\leftarrow nums[j]$。

循环上述过程，直至指针 $i\ge j$，返回操作次数 $ans$ 即可。

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

func minimumOperations(nums []int) int {
	i, j := 0, len(nums)-1
	a, b := nums[i], nums[j]
	ans := 0
	for i < j {
		if a < b {
			i++
			a += nums[i]
			ans++
		} else if b < a {
			j--
			b += nums[j]
			ans++
		} else {
			i, j = i+1, j-1
			a, b = nums[i], nums[j]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2429. 最小异或

中等1 种解法

标签：贪心、位运算

题目、示例与约束

给你两个正整数 num1 和 num2 ，找出满足下述条件的正整数 x ：

• x 的置位数和 num2 相同，且
• x XOR num1 的值 最小

注意 XOR 是按位异或运算。

返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。

整数的 置位数 是其二进制表示中 1 的数目。

 

示例 1：

输入：num1 = 3, num2 = 5
输出：3
解释：
num1 和 num2 的二进制表示分别是 0011 和 0101 。
整数 3 的置位数与 num2 相同，且 3 XOR 3 = 0 是最小的。

示例 2：

输入：num1 = 1, num2 = 12
输出：3
解释：
num1 和 num2 的二进制表示分别是 0001 和 1100 。
整数 3 的置位数与 num2 相同，且 3 XOR 1 = 2 是最小的。

 

提示：

• 1 <= num1, num2 <= 109

方法一：贪心 + 位运算 · Go 实现

思考

$x$ 的置位数必须等于 $num2$，并与 $num1$ 的异或尽量小，即尽量让 $x$ 在高位上对齐 $num1$ 的 $1$。置位数至多 $31$，可按位贪心。

先从高到低占用 $num1$ 已有的 $1$；若名额仍剩，再从低到高填 $num1$ 为 $0$ 的位，以免抬高异或结果。

根据题目描述，我们先求出 $\mathit{\text{nums2}}$ 的置位数 $\mathit{\text{cnt}}$，然后从高位到低位枚举 $\mathit{\text{num1}}$ 的每一位，如果该位为 $1$，则将 $x$ 的对应位设为 $1$，并将 $\mathit{\text{cnt}}$ 减 $1$，直到 $\mathit{\text{cnt}}$ 为 $0$。如果此时 $\mathit{\text{cnt}}$ 仍不为 $0$，则从低位开始将 $\mathit{\text{num1}}$ 的每一位为 $0$ 的位置设为 $1$，并将 $\mathit{\text{cnt}}$ 减 $1$，直到 $\mathit{\text{cnt}}$ 为 $0$。

时间复杂度 $O(\log n)$，其中 $n$ 为 $\mathit{\text{num1}}$ 和 $\mathit{\text{num2}}$ 的最大值。空间复杂度 $O(1)$。

func minimizeXor(num1 int, num2 int) int {
	cnt := bits.OnesCount(uint(num2))
	x := 0
	for i := 30; i >= 0 && cnt > 0; i-- {
		if num1>>i&1 == 1 {
			x |= 1 << i
			cnt--
		}
	}
	for i := 0; cnt > 0; i++ {
		if num1>>i&1 == 0 {
			x |= 1 << i
			cnt--
		}
	}
	return x
}

力扣原题 · Doocs 题解来源

2434. 使用机器人打印字典序最小的字符串

中等1 种解法

标签：栈、贪心、哈希表、字符串

题目、示例与约束

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

• 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
• 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。

请你返回纸上能写出的字典序最小的字符串。

 

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。

示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。

示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。

 

提示：

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

方法一：贪心 + 栈 · Go 实现

思考

$n\le {10}^5$，用栈模拟纸带：字符必须先入栈再弹出到答案。字典序最小意味着能弹出时，若栈顶不大于剩余未读的最小字符，就应立刻弹出。

先计数剩余字符，维护尚未出现的最小字母 $\mathit{\text{mi}}$。依次入栈，并在栈顶 $\le \mathit{\text{mi}}$ 时持续出栈。

题目可以转化为，给定一个字符串序列，在借助一个辅助栈的情况下，将其转化为字典序最小的字符串序列。

我们可以用数组 $\mathit{\text{cnt}}$ 维护字符串 $s$ 中每个字符的出现次数，用栈 $\mathit{\text{stk}}$ 作为题目中的辅助栈，用变量 $\mathit{\text{mi}}$ 维护还未遍历到的字符串中最小的字符。

遍历字符串 $s$，对于每个字符 $c$，我们先将字符 $c$ 在数组 $\mathit{\text{cnt}}$ 中的出现次数减一，更新 $\mathit{\text{mi}}$。然后将字符 $c$ 入栈，此时如果栈顶元素小于等于 $\mathit{\text{mi}}$，则循环将栈顶元素出栈，并将出栈的字符加入答案。

遍历结束，返回答案即可。

时间复杂度 $O(n+|\mathrm{\Sigma }|)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度，而 $|\mathrm{\Sigma }|$ 为字符集大小，本题中 $|\mathrm{\Sigma }|=26$。

func robotWithString(s string) string {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	mi := byte('a')
	stk := []byte{}
	ans := []byte{}
	for i := range s {
		cnt[s[i]-'a']--
		for mi < 'z' && cnt[mi-'a'] == 0 {
			mi++
		}
		stk = append(stk, s[i])
		for len(stk) > 0 && stk[len(stk)-1] <= mi {
			ans = append(ans, stk[len(stk)-1])
			stk = stk[:len(stk)-1]
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

2448. 使数组相等的最小开销

困难2 种解法

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

题目、示例与约束

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。

你可以执行下面操作 任意 次：

• 将 nums 中 任意 元素增加或者减小 1 。

对第 i 个元素执行一次操作的开销是 cost[i] 。

请你返回使 nums 中所有元素 相等 的 最少 总开销。

 

示例 1：

输入：nums = [1,3,5,2], cost = [2,3,1,14]
输出：8
解释：我们可以执行以下操作使所有元素变为 2 ：
- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。

示例 2：

输入：nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出：0
解释：数组中所有元素已经全部相等，不需要执行额外的操作。

 

提示：

• n == nums.length == cost.length
• 1 <= n <= 105
• 1 <= nums[i], cost[i] <= 106
• 测试用例确保输出不超过 2⁵³-1。

方法一：前缀和 + 排序 + 枚举 · Go 实现

思考

把所有数变成同一 $x$ 的代价是 $\sum |a_i-x|b_i$， $n\le {10}^5$ 不能对每个可能 $x$ 暴力。按 $a$ 排序后，代价由左右加权和组成，可用 $a_i{b}_i$ 与 $b_i$ 的前缀和在枚举 $x=a_i$ 时 $O(1)$ 求出。

最优 $x$ 必取某个 $a_i$（分段线性），故枚举排序后的每个位置取最小代价。

我们记数组 nums 所有元素为 $a_1,a_2,\cdots ,a_n$，数组 cost 所有元素为 $b_1,b_2,\cdots ,b_n$。我们不妨令 $a_1\le a_2\le \cdots \le a_n$，即数组 nums 升序排列。

假设我们将数组 nums 中的元素全部变为 $x$，那么我们需要的总开销为：

$$\begin{array}{rl}\sum _{i=1}^n|a_i-x|b_i& =\sum _{i=1}^k(x-a_i)b_i+\sum _{i=k+1}^n(a_i-x)b_i\\ & =x\sum _{i=1}^k{b}_i-\sum _{i=1}^k{a}_i{b}_i+\sum _{i=k+1}^n{a}_i{b}_i-x\sum _{i=k+1}^n{b}_i\end{array}$$

其中 $k$ 为 $a_1,a_2,\cdots ,a_n$ 中小于等于 $x$ 的元素个数。

我们可以使用前缀和的方法，计算 $\sum _{i=1}^k{b}_i$ 和 $\sum _{i=1}^k{a}_i{b}_i$，以及 $\sum _{i=k+1}^n{a}_i{b}_i$ 和 $\sum _{i=k+1}^n{b}_i$。

然后我们枚举 $x$，计算上述四个前缀和，得到上述的总开销，取其中的最小值即可。

时间复杂度 $O(n\times \log n)$。其中 $n$ 为数组 nums 的长度。主要是排序的时间复杂度。

func minCost(nums []int, cost []int) int64 {
	n := len(nums)
	type pair struct{ a, b int }
	arr := make([]pair, n)
	for i, a := range nums {
		b := cost[i]
		arr[i] = pair{a, b}
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i].a < arr[j].a })
	f := make([]int, n+1)
	g := make([]int, n+1)
	for i := 1; i <= n; i++ {
		a, b := arr[i-1].a, arr[i-1].b
		f[i] = f[i-1] + a*b
		g[i] = g[i-1] + b
	}
	var ans int64 = 1e18
	for i := 1; i <= n; i++ {
		a := arr[i-1].a
		l := a*g[i-1] - f[i-1]
		r := f[n] - f[i] - a*(g[n]-g[i])
		ans = min(ans, int64(l+r))
	}
	return ans
}

方法二：排序 + 中位数 · Go 实现

思考

方法一枚举了每个 $a_i$ 作为目标。将 $b_i$ 视为 $a_i$ 的出现次数后，加权中位数即为最优目标，只需找到前缀权超过一半的那个 $a$，再算一次总代价。

我们还可以把 $b_i$ 看作是 $a_i$ 的出现次数，那么中位数下标是 $\frac{\sum _{i=1}^n{b}_i}{2}$。把所有数变成中位数，一定是最优的。

时间复杂度 $O(n\times \log n)$。其中 $n$ 为数组 nums 的长度。主要是排序的时间复杂度。

相似题目：

• 296. 最佳的碰头地点
• 462. 最少移动次数使数组元素相等 II

func minCost(nums []int, cost []int) int64 {
	n := len(nums)
	type pair struct{ a, b int }
	arr := make([]pair, n)
	mid := 0
	for i, a := range nums {
		b := cost[i]
		mid += b
		arr[i] = pair{a, b}
	}
	mid /= 2
	sort.Slice(arr, func(i, j int) bool { return arr[i].a < arr[j].a })
	s, ans := 0, 0
	for _, e := range arr {
		x, c := e.a, e.b
		s += c
		if s > mid {
			for _, t := range arr {
				ans += abs(t.a-x) * t.b
			}
			break
		}
	}
	return int64(ans)

}

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

力扣原题 · Doocs 题解来源

2449. 使数组相似的最少操作次数

困难1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你两个正整数数组 nums 和 target ，两个数组长度相等。

在一次操作中，你可以选择两个 不同 的下标 i 和 j ，其中 0 <= i, j < nums.length ，并且：

• 令 nums[i] = nums[i] + 2 且
• 令 nums[j] = nums[j] - 2 。

如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的。

请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。

 

示例 1：

输入：nums = [8,12,6], target = [2,14,10]
输出：2
解释：可以用两步操作将 nums 变得与 target 相似：
- 选择 i = 0 和 j = 2 ，nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ，nums = [10,14,2] 。
2 次操作是最少需要的操作次数。

示例 2：

输入：nums = [1,2,5], target = [4,1,3]
输出：1
解释：一步操作可以使 nums 变得与 target 相似：
- 选择 i = 1 和 j = 2 ，nums = [1,4,3] 。

示例 3：

输入：nums = [1,1,1,1,1], target = [1,1,1,1,1]
输出：0
解释：数组 nums 已经与 target 相似。

 

提示：

• n == nums.length == target.length
• 1 <= n <= 105
• 1 <= nums[i], target[i] <= 106
• nums 一定可以变得与 target 相似。

方法一：奇偶分类 + 排序 · Go 实现

思考

每次 $\pm 2$ 不改变奇偶，故奇数只能与奇数配对。 $n\le {10}^5$，将两数组按「奇偶、数值」排序后逐对相减，总绝对差除以 $4$ 即为操作次数（一次操作同时改变两个位置各 $2$）。

注意到，由于每次操作，元素的值只会增加 $2$ 或减少 $2$，因此，元素的奇偶性不会改变。

因此，我们可以将数组 $nums$ 和 $target$ 分别按奇偶性分为两组，分别记为 $a_1$ 和 $a_2$，以及 $b_1$ 和 $b_2$。

那么，我们只需要将 $a_1$ 中的元素与 $b_1$ 中的元素配对，将 $a_2$ 中的元素与 $b_2$ 中的元素配对，然后进行操作。配对的过程中，我们可以使用贪心的策略，每次将 $a_i$ 中较小的元素与 $b_i$ 中较小的元素配对，这样可以保证操作的次数最少。这里可以直接通过排序来实现。

由于每次操作，都可以将对应位置的元素差值减少 $4$，因此，我们累计每个对应位置的差值，最后除以 $4$ 即可得到答案。

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

func makeSimilar(nums []int, target []int) int64 {
	sort.Ints(nums)
	sort.Ints(target)
	a1, a2, b1, b2 := []int{}, []int{}, []int{}, []int{}
	for _, v := range nums {
		if v%2 == 0 {
			a1 = append(a1, v)
		} else {
			a2 = append(a2, v)
		}
	}
	for _, v := range target {
		if v%2 == 0 {
			b1 = append(b1, v)
		} else {
			b2 = append(b2, v)
		}
	}
	ans := 0
	for i := 0; i < len(a1); i++ {
		ans += abs(a1[i] - b1[i])
	}
	for i := 0; i < len(a2); i++ {
		ans += abs(a2[i] - b2[i])
	}
	return int64(ans / 4)
}

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

力扣原题 · Doocs 题解来源

2457. 美丽整数的最小增量

中等1 种解法

标签：贪心、数学

题目、示例与约束

给你两个正整数 n 和 target 。

如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个 美丽整数 。

找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

 

示例 1：

输入：n = 16, target = 6
输出：4
解释：最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4 之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。

示例 2：

输入：n = 467, target = 6
输出：33
解释：最初，n 是 467 ，且其每一位数字的和是 4 + 6 + 7 = 17 。在加 33 之后，n 变为 500 且每一位数字的和变成 5 + 0 + 0 = 5 。可以证明无法加上一个小于 33 的非负整数使 n 变成一个美丽整数。

示例 3：

输入：n = 1, target = 1
输出：0
解释：最初，n 是 1 ，且其每一位数字的和是 1 ，已经小于等于 target 。

 

提示：

• 1 <= n <= 1012
• 1 <= target <= 150
• 生成的输入保证总可以使 n 变成一个美丽整数。

方法一：贪心 · Go 实现

思考

$n\le {10}^{12}$，要加尽可能小的 $x$ 使数位和 $\le target$。把最低非零位进位到更高位，数位和会下降，相当于把后缀变成 $0$ 并入上一位。

循环：若 $n+x$ 的数位和仍大，找到最低非零位所在十幂 $p$，令 $x$ 变为「该位以上加一再乘 $p$」减去 $n$。直至数位和合格。

我们定义函数 $f(x)$ 表示一个整数 $x$ 的每一位数字之和，那么题目求的是 $f(n+x)\le target$ 的最小非负整数 $x$。

如果 $y=n+x$ 的每一位数字之和大于 $target$，那么我们可以循环通过以下操作，将 $y$ 的每一位数字之和减小到小于等于 $target$：

• 找到 $y$ 的最低位的非零数字，将其减小到 $0$，并将其高一位的数字加 $1$；
• 更新 $x$，继续上述操作，直到 $n+x$ 的每一位数字之和小于等于 $target$。

循环结束，返回 $x$ 即可。

我们可以举个例子，假设 $n=467$, $target=6$，那么 $n$ 的变化过程如下：

$$\begin{array}{rl}& 467\to 470\to 500\end{array}$$

时间复杂度 $O({\log }^{2}n)$，其中 $n$ 给题目给定的整数。空间复杂度 $O(1)$。

func makeIntegerBeautiful(n int64, target int) (x int64) {
	f := func(x int64) (y int) {
		for ; x > 0; x /= 10 {
			y += int(x % 10)
		}
		return
	}
	for f(n+x) > target {
		y := n + x
		var p int64 = 10
		for y%10 == 0 {
			y /= 10
			p *= 10
		}
		x = (y/10+1)*p - n
	}
	return
}

力扣原题 · Doocs 题解来源

2486. 追加字符以获得子序列

中等1 种解法

标签：贪心、双指针、字符串

题目、示例与约束

给你两个仅由小写英文字母组成的字符串 s 和 t 。

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。

 

示例 1：

输入：s = "coaching", t = "coding"
输出：4
解释：向 s 末尾追加字符串 "ding" ，s = "coachingding" 。
现在，t 是 s ("coachingding") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。

示例 2：

输入：s = "abcde", t = "a"
输出：0
解释：t 已经是 s ("abcde") 的一个子序列。

示例 3：

输入：s = "z", t = "abcde"
输出：5
解释：向 s 末尾追加字符串 "abcde" ，s = "zabcde" 。
现在，t 是 s ("zabcde") 的一个子序列。 
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。

 

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 仅由小写英文字母组成

方法一：双指针 · Go 实现

思考

只能在 $s$ 末尾追加，使 $t$ 成为子序列，追加量即 $t$ 未能被 $s$ 匹配的后缀长度。 $n\le {10}^5$，双指针在 $s$ 上贪心匹配 $t$ 的前缀，返回 $n-j$。

我们定义两个指针 $i$ 和 $j$，分别指向字符串 $s$ 和 $t$ 的首字符。遍历字符串 $s$，如果 $s[i]=t[j]$，则将 $j$ 向后移动一位。最终返回 $n-j$，其中 $n$ 是字符串 $t$ 的长度。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。空间复杂度 $O(1)$。

func appendCharacters(s string, t string) int {
	n, j := len(t), 0
	for _, c := range s {
		if j < n && byte(c) == t[j] {
			j++
		}
	}
	return n - j
}

力扣原题 · Doocs 题解来源

2498. 青蛙过河 II

中等1 种解法

标签：贪心、数组、二分查找

题目、示例与约束

给你一个下标从 0 开始的整数数组 stones ，数组中的元素 严格递增 ，表示一条河中石头的位置。

一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头 至多 到达 一次。

一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。

• 更正式的，如果青蛙从 stones[i] 跳到 stones[j] ，跳跃的长度为 |stones[i] - stones[j]| 。

一条路径的 代价 是这条路径里的 最大跳跃长度 。

请你返回这只青蛙的 最小代价 。

 

示例 1：

输入：stones = [0,2,5,6,7]
输出：5
解释：上图展示了一条最优路径。
这条路径的代价是 5 ，是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径，我们返回 5 。

示例 2：

输入：stones = [0,3,9]
输出：9
解释：
青蛙可以直接跳到最后一块石头，然后跳回第一块石头。
在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
这是可行路径中的最小代价。

 

提示：

• 2 <= stones.length <= 105
• 0 <= stones[i] <= 109
• stones[0] == 0
• stones 中的元素严格递增。

方法一：脑筋急转弯 · Go 实现

思考

去程与回程必须访问所有石块且方向各一次，最小化最大跳距。 $n\le {10}^5$，最优是间隔跳：去程走偶数下标，回程走奇数（或反之），最大跨度即相邻隔一块的距离，还要计入第一步 $stones[1]-stones[0]$。

要使得跳跃过程中的每一步的最大跳跃长度最小，我们应该将跳跃过程切分成尽可能多的连续的步骤。通过观察，间隔跳跃可以获取最优解。

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

func maxJump(stones []int) int {
	ans := stones[1] - stones[0]
	for i := 2; i < len(stones); i++ {
		ans = max(ans, stones[i]-stones[i-2])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2499. 让数组不相等的最小总代价

困难1 种解法

标签：贪心、数组、哈希表、计数

题目、示例与约束

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。

每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。

你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。

请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。

 

示例 1：

输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
输出：10
解释：
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。

示例 2：

输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
输出：10
解释：
实现目标的一种方法为：
- 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。
- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。
总代价为 10 ，是所有方案中的最小代价。

示例 3：

输入：nums1 = [1,2,2], nums2 = [1,2,2]
输出：-1
解释：
不管怎么操作，都无法满足题目要求。
所以返回 -1 。

 

提示：

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

方法一：贪心 · Go 实现

思考

相等位置必须换出去，下标之和先计入这些强制交换。若某值在强制位置中超过一半，则无法在内部两两交换消化，还得到其他位置找与该值无关的一对，再累加那些下标。

先统计 $a_i=b_i$ 的次数；若最大频次 $v$ 满足 $2v>same$，超额 $2v-same$ 必须向外交换。再扫 $a\ne b$ 且两端都不是该主导值的位置。仍有剩余则无解。

我们先同时遍历数组 nums1 和 nums2，统计相同位置上的值相同的个数 same，这些位置上的值必须交换，因此，将这些位置下标累加到答案中。另外，用数组或哈希表 cnt 统计这些相同值的出现次数。

如果所有相同值的出现次数均不超过 same 的一半，那么意味着，我们可以在其内部，通过两两交换，使得对应位置上的值不同，而这些交换，已经在上面累加下标时计入了答案中了，无需额外的代价。否则，如果某个值的出现次数超过 same 的一半，那么对于这个值就是多出的个数，我们需要在数组的其他位置上找到合适的，进行交换。这里我们可以直接遍历一遍数组得出。

如果最终还有剩余位置未能交换，说明无法达成目标，返回 $-1$ 即可，否则返回答案。

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

func minimumTotalCost(nums1 []int, nums2 []int) (ans int64) {
	same, n := 0, len(nums1)
	cnt := make([]int, n+1)
	for i, a := range nums1 {
		b := nums2[i]
		if a == b {
			same++
			ans += int64(i)
			cnt[a]++
		}
	}
	var m, lead int
	for i, v := range cnt {
		if t := v*2 - same; t > 0 {
			m = t
			lead = i
			break
		}
	}
	for i, a := range nums1 {
		b := nums2[i]
		if m > 0 && a != b && a != lead && b != lead {
			ans += int64(i)
			m--
		}
	}
	if m > 0 {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2517. 礼盒的最大甜蜜度

中等1 种解法

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

题目、示例与约束

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

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

思考

礼盒的甜蜜度是所选 $k$ 个价格中任意两两差的最小值，要求该最小值尽量大。枚举子集在 $n\le {10}^5$ 时不可行。

若甜蜜度 $x$ 可达，则更小的值也可达，故对 $x$ 二分。排序后从左到右贪心：与上一所选价格之差至少为 $x$ 就选，能选出 $k$ 个则 $x$ 可行。上界为最大价与最小价之差。

我们注意到，如果一个甜蜜度为 $x$ 的礼盒是可行的，那么甜蜜度小于 $x$ 的礼盒也是可行的，这存在着单调性，因此我们可以使用二分查找的方法，找到最大的可行甜蜜度。

我们首先将数组 $price$ 排序，然后定义二分查找的左边界 $l=0$, $r=price[n-1]-price[0]$。每一次，我们计算出当前的中间值 $mid=\lfloor \frac{l+r+1}{2}\rfloor$，以 $mid$ 作为甜蜜度，判断是否可行。若可行，那么我们将左边界 $l$ 更新为 $mid$，否则将右边界 $r$ 更新为 $mid-1$。最后返回 $l$ 即可。

那么问题的关键转化为：判断一个甜蜜度是否可行，我们通过函数 $check(x)$ 来实现。函数 $check(x)$ 的执行逻辑如下：

定义一个变量 $cnt$ 表示当前已经选取的糖果的数量，初始值为 $0$，定义一个变量 $pre$ 表示上一个选取的糖果的价格，初始值为 $-x$。然后我们遍历排好序的数组 $price$，对于每一个糖果的价格 $cur$，如果 $cur-pre\ge x$，那么我们就选取这个糖果，将 $pre$ 更新为 $cur$，并将 $cnt$ 加一。最后判断 $cnt$ 是否大于等于 $k$，如果是，那么返回 $true$，否则返回 $false$。

时间复杂度 $O(n\times (\log n+\log M))$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $price$ 的长度；而 $M$ 是数组 $price$ 中的最大值，本题中 $M\le {10}^9$。

func maximumTastiness(price []int, k int) int {
	sort.Ints(price)
	return sort.Search(price[len(price)-1], func(x int) bool {
		cnt, pre := 0, -x
		for _, cur := range price {
			if cur-pre >= x {
				pre = cur
				cnt++
			}
		}
		return cnt < k
	}) - 1
}

力扣原题 · Doocs 题解来源

2528. 最大化城市的最小电量

困难1 种解法

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

题目、示例与约束

给你一个下标从 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.length
• 1 <= n <= 105
• 0 <= stations[i] <= 105
• 0 <= r <= n - 1
• 0 <= k <= 109

方法一：二分查找 + 差分数组 + 贪心 · Go 实现

思考

一座电站覆盖半径 $r$ 内的城市，还可再新建至多 $k$ 座，目标是最大化“供电最少的那座城市”的电量。 $n\le {10}^5$，不能对每个 $k$ 的分配方案搜索。

最小电量对新建数量单调，故二分目标值 $x$。差分数组先算出每座城市的初始供电。检验时从左到右：当前城市不足 $x$ 则把缺口建在能覆盖它的最右侧，使后续城市尽量受益，并用差分数组记录这段增量。缺口超过剩余 $k$ 则 $x$ 不可行。

根据题目描述，最小供电站数目随着 $k$ 值的增大而增大，因此，我们可以用二分查找，找到一个最大的最小供电站数目，并且需要额外建造的供电站不超过 $k$ 座。

我们先利用差分数组以及前缀和算出初始时每座城市的供电站数目，记录在数组 $s$ 中，其中 $s[i]$ 表示第 $i$ 座城市的供电站数目。

接下来，我们定义二分查找的左边界为 $0$，右边界为 $2^{40}$。然后实现一个 $check(x,k)$ 函数，用于判断是否城市供电站数目的最小值是否可以为 $x$，使得额外建造的供电站不超过 $k$ 座。

函数 $check(x,k)$ 的实现逻辑是：

遍历每座城市，如果当前城市 $i$ 的供电站数目小于 $x$，此时我们可以贪心地在尽可能右边的位置上建造供电站，位置 $j=min(i+r,n-1)$，这样可以使得供电站覆盖尽可能多的城市。过程中我们可以借助差分数组，给一段连续的位置加上某个值。如果需要额外建造的供电站数量超过 $k$，那么 $x$ 不满足条件，返回 false。否则遍历结束后，返回 true。

时间复杂度 $O(n\times \log M)$，空间复杂度 $O(n)$。其中 $n$ 为城市数量，而 $M$ 我们固定取 $2^{40}$。

func maxPower(stations []int, r int, k int) int64 {
	n := len(stations)
	d := make([]int, n+1)
	s := make([]int, n+1)
	for i, v := range stations {
		left, right := max(0, i-r), min(i+r, n-1)
		d[left] += v
		d[right+1] -= v
	}
	s[0] = d[0]
	for i := 1; i < n+1; i++ {
		s[i] = s[i-1] + d[i]
	}
	check := func(x, k int) bool {
		d := make([]int, n+1)
		t := 0
		for i := range stations {
			t += d[i]
			dist := x - (s[i] + t)
			if dist > 0 {
				if k < dist {
					return false
				}
				k -= dist
				j := min(i+r, n-1)
				left, right := max(0, j-r), min(j+r, n-1)
				d[left] += dist
				d[right+1] -= dist
				t += dist
			}
		}
		return true
	}
	left, right := 0, 1<<40
	for left < right {
		mid := (left + right + 1) >> 1
		if check(mid, k) {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return int64(left)
}

力扣原题 · Doocs 题解来源

2530. 执行 K 次操作后的最大分数

中等1 种解法

标签：贪心、数组、堆（优先队列）

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

1. 选出一个满足 0 <= i < nums.length 的下标 i ，
2. 将你的 分数 增加 nums[i] ，并且
3. 将 nums[i] 替换为 ceil(nums[i] / 3) 。

返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

 

示例 1：

输入：nums = [10,10,10,10,10], k = 5
输出：50
解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

示例 2：

输入：nums = [1,10,3,3,3], k = 3
输出：17
解释：可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,2,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。

 

提示：

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

方法一：优先队列（大根堆） · Go 实现

思考

每次把当前最大值 $v$ 加入分数并改成 $\lceil v/3\rceil$，重复 $k$ 次。若每次扫描数组找最大， $k$ 与 $n$ 达 ${10}^5$ 时为平方级。

大根堆始终给出当前最大者：弹出 $v$，累加后再把 $\lceil v/3\rceil$ 压回。Python 用相反数模拟大根堆，共 $k$ 次对数操作。

要使得分数最大化，我们需要在每一步操作中，选择元素值最大的元素进行操作。因此，我们可以使用优先队列（大根堆）来维护当前元素值最大的元素。

每次从优先队列中取出元素值最大的元素 $v$，将答案加上 $v$，并将 $v$ 替换为 $\lceil \frac{v}{3}\rceil$，加入优先队列。重复 $k$ 次后，将答案返回即可。

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

func maxKelements(nums []int, k int) (ans int64) {
	h := hp{nums}
	heap.Init(&h)
	for ; k > 0; k-- {
		ans += int64(h.IntSlice[0])
		h.IntSlice[0] = (h.IntSlice[0] + 2) / 3
		heap.Fix(&h, 0)
	}
	return
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (hp) Push(any)             {}
func (hp) Pop() (_ any)         { return }

力扣原题 · Doocs 题解来源

2541. 使数组中所有元素相等的最小操作数 II

中等1 种解法

标签：贪心、数组、数学

题目、示例与约束

给你两个整数数组 nums1 和 nums2 ，两个数组长度都是 n ，再给你一个整数 k 。你可以对数组 nums1 进行以下操作：

• 选择两个下标 i 和 j ，将 nums1[i] 增加 k ，将 nums1[j] 减少 k 。换言之，nums1[i] = nums1[i] + k 且 nums1[j] = nums1[j] - k 。

如果对于所有满足 0 <= i < n 都有 num1[i] == nums2[i] ，那么我们称 nums1 等于 nums2 。

请你返回使 nums1 等于 nums2 的 最少 操作数。如果没办法让它们相等，请你返回 -1 。

 

示例 1：

输入：nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
输出：2
解释：我们可以通过 2 个操作将 nums1 变成 nums2 。
第 1 个操作：i = 2 ，j = 0 。操作后得到 nums1 = [1,3,4,4] 。
第 2 个操作：i = 2 ，j = 3 。操作后得到 nums1 = [1,3,7,1] 。
无法用更少操作使两个数组相等。

示例 2：

输入：nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
输出：-1
解释：无法使两个数组相等。

 

提示：

• n == nums1.length == nums2.length
• 2 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 109
• 0 <= k <= 105

方法一：一次遍历 · Go 实现

思考

一次操作把某一位加 $k$ 并把另一位减 $k$，即总量守恒。若某位差值不能被 $k$ 整除，或 $k=0$ 却仍有不等，则无法对齐。

统计需要“加 $k$”的次数 $a$ 与“减 $k$”的次数 $b$。操作成对出现，故仅当 $a=b$ 时可行，答案为 $a$。

我们用两个变量 $a$ 和 $b$ 分别记录将 $\mathit{\text{nums1}}$ 中的元素增加 $k$ 和减少 $k$ 的次数。

我们遍历两个数组，如果两个指针指向的元素相等，则继续；如果两个指针指向的元素不相等，则如果 $k$ 等于 $0$ 或者两个元素之差不能被 $k$ 整除，则返回 $-1$；否则将两个元素之差除以 $k$ 得到操作数 $t$，如果 $t$ 小于 $0$，则将 $-t$ 加到 $a$ 上，否则将 $t$ 加到 $b$ 上。

最后如果 $a$ 和 $b$ 相等，则返回 $a$，否则返回 $-1$。

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

func minOperations(nums1 []int, nums2 []int, k int) int64 {
	var a, b int64
	for i, x := range nums1 {
		y := nums2[i]
		if x == y {
			continue
		}
		if k == 0 || (x-y)%k != 0 {
			return -1
		}
		t := (x - y) / k
		if t < 0 {
			a += int64(-t)
		} else {
			b += int64(t)
		}
	}
	if a == b {
		return a
	}
	return -1
}

力扣原题 · Doocs 题解来源

2542. 最大子序列的分数

中等1 种解法

标签：贪心、数组、排序、堆（优先队列）

题目、示例与约束

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。

对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：

• nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
• 用公式表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。

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

一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。

 

示例 1：

输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
输出：12
解释：
四个可能的子序列分数为：
- 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
- 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
- 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
- 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
所以最大分数为 12 。

示例 2：

输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
输出：30
解释：
选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。

 

提示：

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

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

思考

从下标中选 $k$ 个，得分是 $\mathit{\text{nums1}}$ 所选之和乘以 $\mathit{\text{nums2}}$ 所选的最小值。枚举全部 $k$ 元子集不可行。

若最小值被定为某个 $a$，则只能在 $\mathit{\text{nums2}}\ge a$ 的位置中选 $k$ 个 $\mathit{\text{nums1}}$。按 $\mathit{\text{nums2}}$ 降序扫描时，最小值恰好是当前的 $a$，前面的候选都合法。小根堆保留最大的 $k$ 个 $\mathit{\text{nums1}}$，堆满时用和乘 $a$ 更新答案并弹出最小者，为后续腾出位置。

将 nums2 与 nums1 按照 nums2 降序排序，然后从前往后遍历，维护一个小根堆，堆中存储 nums1 中的元素，堆中元素个数不超过 $k$ 个，同时维护一个变量 $s$，表示堆中元素的和，遍历过程中不断更新答案。

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

func maxScore(nums1 []int, nums2 []int, k int) int64 {
	type pair struct{ a, b int }
	nums := []pair{}
	for i, a := range nums1 {
		b := nums2[i]
		nums = append(nums, pair{a, b})
	}
	sort.Slice(nums, func(i, j int) bool { return nums[i].b > nums[j].b })
	q := hp{}
	var ans, s int
	for _, e := range nums {
		a, b := e.a, e.b
		s += a
		heap.Push(&q, a)
		if q.Len() == k {
			ans = max(ans, s*b)
			s -= heap.Pop(&q).(int)
		}
	}
	return int64(ans)
}

type hp struct{ sort.IntSlice }

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

力扣原题 · Doocs 题解来源

2548. 填满背包的最大价格 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给定一个二维整数数组 items ，其中 items[i] = [pricei, weighti] 表示第 i 个物品的价格和重量。

还给定一个 正 整数容量 capacity 。

每个物品可以分成两个部分，比率为 part1 和 part2 ，其中 part1 + part2 == 1 。

• 第一个物品的重量是 weighti * part1 ，价格是 pricei * part1 。
• 同样，第二个物品的重量是 weighti * part2 ，价格是 pricei * part2 。

使用给定的物品，返回填满容量为 capacity 的背包所需的 最大总价格 。如果无法填满背包，则返回 -1 。与实际答案的差距在 10-5 以内的 实际答案 将被视为接受。

 

示例 1 ：

输入：items = [[50,1],[10,8]], capacity = 5
输出：55.00000
解释：
我们将第二个物品分成两个部分，part1 = 0.5，part2 = 0.5。 
第一个物品的价格和重量分别为 5 和 4 。同样地，第二个物品的价格和重量也是 5 和 4 。 
经过操作后，数组 items 变为 [[50,1],[5,4],[5,4]] 。 
为了填满容量为 5 的背包，我们取价格为 50 的第一个元素和价格为 5 的第二个元素。 
可以证明，55.0 是我们可以达到的最大总价值。

示例 2 ：

输入：items = [[100,30]], capacity = 50
输出：-1.00000
解释：无法用给定的物品装满背包。

 

提示：

• 1 <= items.length <= 105
• items[i].length == 2
• 1 <= pricei, weighti <= 104
• 1 <= capacity <= 109

方法一：贪心 + 排序 · Go 实现

思考

物品可按重量比例取用，容量固定，要最大化总价；装不满则返回 $-1$。这是分数背包：单位价格高的应优先取。

按 $w/p$（即单位价的倒数）升序等价于按单位价降序。依次取 $min(w,\mathit{\text{capacity}})$，累加对应价格；容量仍剩余说明总重量不足。

我们将物品按照单位价格从大到小排序，然后依次取出物品，直到背包装满。

若最后背包未装满，则返回 $-1$，否则返回总价格。

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

func maxPrice(items [][]int, capacity int) (ans float64) {
	sort.Slice(items, func(i, j int) bool { return items[i][1]*items[j][0] < items[i][0]*items[j][1] })
	for _, e := range items {
		p, w := e[0], e[1]
		v := min(w, capacity)
		ans += float64(v) / float64(w) * float64(p)
		capacity -= v
	}
	if capacity > 0 {
		return -1
	}
	return
}

力扣原题 · Doocs 题解来源

2551. 将珠子放入背包中

困难1 种解法

标签：贪心、数组、排序、堆（优先队列）

题目、示例与约束

你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 。

请你按照如下规则将所有的珠子放进 k 个背包。

• 没有背包是空的。
• 如果第 i 个珠子和第 j 个珠子在同一个背包里，那么下标在 i 到 j 之间的所有珠子都必须在这同一个背包中。
• 如果一个背包有下标从 i 到 j 的所有珠子，那么这个背包的价格是 weights[i] + weights[j] 。

一个珠子分配方案的 分数 是所有 k 个背包的价格之和。

请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。

 

示例 1：

输入：weights = [1,3,5,1], k = 2
输出：4
解释：
分配方案 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6 。
分配方案 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10 。
所以差值为 10 - 6 = 4 。

示例 2：

输入：weights = [1, 3], k = 2
输出：0
解释：唯一的分配方案为 [1],[3] 。
最大最小得分相等，所以返回 0 。

 

提示：

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

方法一：问题转化 + 排序 · Go 实现

思考

把大理石按顺序分成 $k$ 段，一段代价是两端重量之和，求最大总分与最小总分之差。首尾两颗始终计入，中间每切一刀在相邻对 $w_i+w_{i+1}$ 上加一次。

因此切点互不影响。把所有相邻和排序，最大的 $k-1$ 个之和减去最小的 $k-1$ 个之和即为两端固定贡献抵消后的差值。

我们可以将问题转化为：将数组 weights 分成 $k$ 个连续的子数组，也就是说，我们要找到 $k-1$ 个分割点，每个分割点的价格是分割点左右两个元素的和，求最大的 $k-1$ 个分割点的价格之和与最小的 $k-1$ 个分割点的价格之和的差值，即为答案。

因此，我们可以处理数组 weights，将其转化为一个长度为 $n-1$ 的数组 arr，其中 arr[i] = weights[i] + weights[i+1]，然后对数组 arr 进行排序，最后求出最大的 $k-1$ 个分割点的价格之和与最小的 $k-1$ 个分割点的价格之和的差值即可。

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

func putMarbles(weights []int, k int) (ans int64) {
	n := len(weights)
	arr := make([]int, n-1)
	for i, w := range weights[:n-1] {
		arr[i] = w + weights[i+1]
	}
	sort.Ints(arr)
	for i := 0; i < k-1; i++ {
		ans += int64(arr[n-2-i] - arr[i])
	}
	return
}

力扣原题 · Doocs 题解来源

2554. 从一个范围内选择最多整数 I

中等2 种解法

标签：贪心、数组、哈希表、二分查找、排序

题目、示例与约束

给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：

• 被选择整数的范围是 [1, n] 。
• 每个整数 至多 选择 一次 。
• 被选择整数不能在数组 banned 中。
• 被选择整数的和不超过 maxSum 。

请你返回按照上述规则 最多 可以选择的整数数目。

 

示例 1：

输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：你可以选择整数 2 和 4 。
2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。

示例 2：

输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
解释：按照上述规则无法选择任何整数。

示例 3：

输入：banned = [11], n = 7, maxSum = 50
输出：7
解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。

 

提示：

• 1 <= banned.length <= 104
• 1 <= banned[i], n <= 104
• 1 <= maxSum <= 109

方法一：贪心 + 枚举 · Go 实现

思考

从 $[1,n]$ 中选尽可能多的互异整数，避开 $\mathit{\text{banned}}$，且和不超过 $\mathit{\text{maxSum}}$。选小数更利于多选，故从 $1$ 起贪心。

$n\le {10}^4$ 时枚举每个候选，用集合判禁并累加，和一旦超限即停。

我们用变量 $s$ 表示当前已经选择的整数的和，用变量 $ans$ 表示当前已经选择的整数的个数。将数组 banned 转换为哈希表，方便判断某个整数是否不可选。

接下来，我们从 $1$ 开始枚举整数 $i$，如果 $s+i\le maxSum$ 且 $i$ 不在 banned 中，那么我们就可以选择整数 $i$，并将 $s$ 和 $ans$ 分别加上 $i$ 和 $1$。

最终，我们返回 $ans$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为给定的整数。

func maxCount(banned []int, n int, maxSum int) (ans int) {
	ban := map[int]bool{}
	for _, x := range banned {
		ban[x] = true
	}
	s := 0
	for i := 1; i <= n && s+i <= maxSum; i++ {
		if !ban[i] {
			ans++
			s += i
		}
	}
	return
}

方法二：贪心 + 二分查找 · Go 实现

思考

方法一的时间随 $n$ 线性增长，在 $n$ 更大的变体中不可用。禁选点把 $[1,n]$ 切成若干连续段，段内前缀和是等差数列，可二分这段能取多少个。从左到右取满能取的，直到额度用尽。

如果 $n$ 很大，那么方法一中的枚举会超时。

我们可以在数组 banned 中加入 $0$ 和 $n+1$，并将数组 banned 去重且移除大于 $n+1$ 的元素，然后进行排序。

接下来，我们枚举数组 banned 中的每两个相邻元素 $i$ 和 $j$，那么可选的整数范围就是 $[i+1,j-1]$。二分枚举我们在此区间内能够选择的元素个数，找到最大的可选元素个数，然后将其加到 $ans$ 中。同时在 maxSum 中减去这些元素的和。如果 maxSum 小于 $0$，那么我们跳出循环。返回答案即可。

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

相似题目：

• 2557. 从一个范围内选择最多整数 II

func maxCount(banned []int, n int, maxSum int) (ans int) {
	banned = append(banned, []int{0, n + 1}...)
	sort.Ints(banned)
	ban := []int{}
	for i, x := range banned {
		if (i > 0 && x == banned[i-1]) || x > n+1 {
			continue
		}
		ban = append(ban, x)
	}
	for k := 1; k < len(ban); k++ {
		i, j := ban[k-1], ban[k]
		left, right := 0, j-i-1
		for left < right {
			mid := (left + right + 1) >> 1
			if (i+1+i+mid)*mid/2 <= maxSum {
				left = mid
			} else {
				right = mid - 1
			}
		}
		ans += left
		maxSum -= (i + 1 + i + left) * left / 2
		if maxSum <= 0 {
			break
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2557. 从一个范围内选择最多整数 II 🔒

中等1 种解法

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

题目、示例与约束

给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：

• 被选择整数的范围是 [1, n] 。
• 每个整数 至多 选择 一次 。
• 被选择整数不能在数组 banned 中。
• 被选择整数的和不超过 maxSum 。

请你返回按照上述规则 最多 可以选择的整数数目。

 

示例 1：

输入：banned = [1,4,6], n = 6, maxSum = 4
输出：1
解释：你可以选择整数 3 。
3 在范围 [1, 6] 内，且不在 banned 中，所选整数的和为 3 ，也没有超过 maxSum 。

示例 2：

输入：banned = [4,3,5,6], n = 7, maxSum = 18
输出：3
解释：你可以选择整数 1, 2 和 7 。
它们都在范围 [1, 7] 中，且都没出现在 banned 中，所选整数的和为 10 ，没有超过 maxSum 。

 

提示：

• 1 <= banned.length <= 105
• 1 <= banned[i] <= n <= 109
• 1 <= maxSum <= 1015

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

思考

题意与“范围 I”相同，但 $n$ 与 $\mathit{\text{maxSum}}$ 大到不能从 $1$ 枚举到 $n$。

把 $0$ 与 $n+1$ 并入禁选集合并排序后，相邻禁选点之间是连续可选段。段内前 $t$ 个数的和为等差公式，对 $t$ 二分即可在对数时间内取满当前额度，从左向右直到和用尽。

我们可以在数组 banned 中加入 $0$ 和 $n+1$，将数组 banned 去重并排序。

接下来，我们枚举数组 banned 中的每两个相邻元素 $i$ 和 $j$，那么可选的整数范围就是 $[i+1,j-1]$。二分枚举我们在此区间内能够选择的元素个数，找到最大的可选元素个数，然后将其加到 $ans$ 中。同时在 maxSum 中减去这些元素的和。如果 maxSum 小于 $0$，那么我们跳出循环。返回答案即可。

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

func maxCount(banned []int, n int, maxSum int64) (ans int) {
	banned = append(banned, []int{0, n + 1}...)
	sort.Ints(banned)
	ban := []int{}
	for i, x := range banned {
		if i > 0 && x == banned[i-1] {
			continue
		}
		ban = append(ban, x)
	}
	for k := 1; k < len(ban); k++ {
		i, j := ban[k-1], ban[k]
		left, right := 0, j-i-1
		for left < right {
			mid := (left + right + 1) >> 1
			if int64((i+1+i+mid)*mid/2) <= maxSum {
				left = mid
			} else {
				right = mid - 1
			}
		}
		ans += left
		maxSum -= int64((i + 1 + i + left) * left / 2)
		if maxSum <= 0 {
			break
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2561. 重排水果

困难1 种解法

标签：贪心、排序、数组、哈希表

题目、示例与约束

你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的交换成本。你想要让两个果篮相等。为此，可以根据需要多次执行下述操作：

• 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
• 交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。

 

示例 1：

输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。

示例 2：

输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。

 

提示：

• basket1.length == basket2.length
• 1 <= basket1.length <= 105
• 1 <= basket1i,basket2i <= 109

方法一：贪心 + 构造 · Go 实现

思考

交换两篮中的水果使两边多重集相同，一次代价为二者较小值。先对每个取值做差：一侧多出的必须与另一侧多出的对换。差为奇数则无解。

需要换出的水果按值排序后，较小的一半应与较大的一半配对。直接交换代价是较小者本身；也可借全局最小水果 $mi$ 中转两次，代价 $2mi$。对较小一半取 $min(x,2mi)$ 之和。

我们可以先将两个数组中共有的元素去掉，对于剩下的每个数字，其出现的次数必须为偶数，否则无法构造出相同的数组。不妨记去除共有元素后，两数组分别为 $a$ 和 $b$。

接下来，我们考虑如何进行交换。

如果我们要交换 $a$ 中最小的数，那么我们要在 $b$ 中找到最大的数，与其进行交换；同理，如果我们要交换 $b$ 中最小的数，那么我们要在 $a$ 中找到最大的数，与其进行交换。可以通过排序来实现。

不过，还有另一种交换的方案，我们可以借助一个最小的数 $mi$ 作为过渡元素，将 $a$ 中的数先与 $mi$ 进行交换，再将 $mi$ 与 $b$ 中的数进行交换。这样，交换的成本为 $2\times mi$。

在代码实现上，我们可以直接将数组 $a$ 和 $b$ 合并成数组 $nums$，然后对数组 $nums$ 进行排序。接下来枚举前一半的数，计算每次的最小成本，累加到答案中即可。

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

func minCost(basket1 []int, basket2 []int) (ans int64) {
	cnt := map[int]int{}
	for i, a := range basket1 {
		cnt[a]++
		cnt[basket2[i]]--
	}
	mi := 1 << 30
	nums := []int{}
	for x, v := range cnt {
		if v%2 != 0 {
			return -1
		}
		for i := abs(v) / 2; i > 0; i-- {
			nums = append(nums, x)
		}
		mi = min(mi, x)
	}
	sort.Ints(nums)
	m := len(nums)
	for i := 0; i < m/2; i++ {
		ans += int64(min(nums[i], mi*2))
	}
	return
}

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

力扣原题 · Doocs 题解来源

2566. 替换一个数字后的最大差值

简单1 种解法

标签：贪心、数学

题目、示例与约束

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差为多少。

注意：

• 当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 num 中所有 d1 都替换成 d2 。
• Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
• Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
• 替换后得到的数字可以包含前导 0 。
• Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。

 

示例 1：

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2：

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。

 

提示：

• 1 <= num <= 108

方法一：贪心 · Go 实现

思考

把某一种数字一律改成另一个数字，分别得到尽可能大与尽可能小的结果，求二者之差。位数很少，枚举被改数字与目标数字亦可，但最优改法是确定的。

最小数把最高位那种数字全部改成 $0$；最大数把从左起第一个非 $9$ 的数字全部改成 $9$。若已全是 $9$，最大值就是自身。

我们先将数字转为字符串 $s$。

要得到最小值，我们只需要将找到字符串 $s$ 的第一个数字 $s[0]$，然后把字符串中所有的 $s[0]$ 替换成 $0$ 即可。

要得到最大值，我们需要找到字符串 $s$ 中第一个不是 $9$ 的数字 $s[i]$，然后把字符串中所有的 $s[i]$ 替换成 $9$ 即可。

最后返回最大值和最小值的差即可。

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数字 $\mathit{\text{num}}$ 的值。

func minMaxDifference(num int) int {
	s := []byte(strconv.Itoa(num))
	first := s[0]
	for i := range s {
		if s[i] == first {
			s[i] = '0'
		}
	}
	mi, _ := strconv.Atoi(string(s))
	t := []byte(strconv.Itoa(num))
	for i := range t {
		if t[i] != '9' {
			second := t[i]
			for j := i; j < len(t); j++ {
				if t[j] == second {
					t[j] = '9'
				}
			}
			mx, _ := strconv.Atoi(string(t))
			return mx - mi
		}
	}
	return num - mi
}

力扣原题 · Doocs 题解来源

2567. 修改两个元素的最小分数

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。

• nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
• nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
• nums 的分数是 最大 得分与 最小 得分的和。

我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。

请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。

|x| 表示 x 的绝对值。

 

示例 1：

输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。

示例 2：

输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。

 

提示：

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

方法一：排序 + 贪心 · Go 实现

思考

数组得分是“相邻差的最小值”加“最大最小之差”。可改至多两个元素。把某元素改成已有值即可让低分变成 $0$，于是得分只剩极差。

排序后，改两个数等价于丢掉两端各若干个极值。三种丢掉方式覆盖全部最优：丢掉两个最小、各丢一端、丢掉两个最大，取三种极差的最小者。

根据题意我们知道，最小得分实际上是排序数组相邻两个元素的最小差值，最大得分是排序数组首尾元素的差值。数组 $nums$ 的分数是最小得分与最大得分的和。

因此，我们可以先对数组进行排序。由于题目允许我们修改数组中最多两个元素的值，我们可以通过修改一个数，让其跟数组中的另一个数相同，使得最小得分为 $0$，那么数组 $nums$ 的分数实际上就是最大得分。我们可以选择进行如下修改之一：

1. 修改最小的两个数为 $nums[2]$，那么最大得分为 $nums[n-1]-nums[2]$；
2. 修改最小的一个数为 $nums[1]$，最大的一个数为 $nums[n-2]$，那么最大得分为 $nums[n-2]-nums[1]$；
3. 修改最大的两个数为 $nums[n-3]$，那么最大得分为 $nums[n-3]-nums[0]$。

最后，我们返回上述三种修改的得分的最小值即可。

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

相似题目：

• 1509. 三次操作后最大值与最小值的最小差

func minimizeSum(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	return min(nums[n-1]-nums[2], min(nums[n-2]-nums[1], nums[n-3]-nums[0]))
}

力扣原题 · Doocs 题解来源