LeetCode Go · 贪心（9）

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

来源与许可

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

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

2576. 求出最多标记下标

中等1 种解法

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

题目、示例与约束

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

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

• 选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

 

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。

示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。

 

提示：

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

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

思考

一对可标记当且仅当较小者的两倍不超过较大者，每个下标至多用一次，求最多标记个数。配对数量至多为 $\lfloor n/2\rfloor$，应让较小的一半去配较大的一半。

排序后，左指针停在较小一半，右半从中位数之后扫过：当前值至少是左值的两倍则配对成功并右移左指针。答案为成功次数的两倍。

根据题目描述，题目最多产生 $n/2$ 组标记，其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

为了将下标尽可能多地标记，我们可以将数组 $\mathit{\text{nums}}$ 排序，接下来，我们遍历右半部分的每个元素 $\mathit{\text{nums}}[j]$，用一个指针 $\mathit{\text{i}}$ 指向左半部分的最小元素，如果 $\mathit{\text{nums}}[i]\times 2\le \mathit{\text{nums}}[j]$，则可以标记下标 $\mathit{\text{i}}$ 和 $\mathit{\text{j}}$，我们将 $\mathit{\text{i}}$ 向右移动一个位置。继续遍历右半部分的元素，直到到达数组的末尾。此时，我们可以标记的下标数目为 $\mathit{\text{i}}\times 2$。

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

func maxNumOfMarkedIndices(nums []int) (ans int) {
	sort.Ints(nums)
	i, n := 0, len(nums)
	for _, x := range nums[(n+1)/2:] {
		if nums[i]*2 <= x {
			i++
		}
	}
	return i * 2
}

力扣原题 · Doocs 题解来源

2578. 最小和分割

简单2 种解法

标签：贪心、数学、排序

题目、示例与约束

给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。
  • 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
• num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

注意：

• num 保证没有前导 0 。
• num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

 

示例 1：

输入：num = 4325
输出：59
解释：我们可以将 4325 分割成 num1 = 24 和 num2 = 35 ，和为 59 ，59 是最小和。

示例 2：

输入：num = 687
输出：75
解释：我们可以将 687 分割成 num1 = 68 和 num2 = 7 ，和为最优值 75 。

 

提示：

• 10 <= num <= 109

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

思考

把 $num$ 的数位分成两个整数，使二者之和最小。高位应尽量小，故较小的数位应轮流放到两个数的高位。

统计 $0$– $9$ 的次数后，从小到大交替接到两个数的末尾，等价于让两个数的位数尽量接近且高位都尽量小。

我们先用哈希表或数组 $cnt$ 统计 $num$ 中各个数字出现的次数，用变量 $n$ 记录 $num$ 的位数。

接下来，枚举 $nums$ 所有位数 $i$，将 $cnt$ 中的数字按照从小到大的顺序交替地分配给 $num1$ 和 $num2$，记录在一个长度为 $2$ 的数组 $ans$ 中。最后，返回 $ans$ 中的两个数之和即可。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为 $num$ 的位数；而 $C$ 为 $num$ 中不同数字的个数，本题中 $C\le 10$。

func splitNum(num int) int {
	cnt := [10]int{}
	n := 0
	for ; num > 0; num /= 10 {
		cnt[num%10]++
		n++
	}
	ans := [2]int{}
	for i, j := 0, 0; i < n; i++ {
		for cnt[j] == 0 {
			j++
		}
		cnt[j]--
		ans[i&1] = ans[i&1]*10 + j
	}
	return ans[0] + ans[1]
}

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

思考

方法一用手写计数保证线性。位数至多十位，排序字符串后取偶数位与奇数位分别拼成两个整数，分配规则相同，实现更短。

我们可以将 $num$ 转换成字符串或者字符数组，然后对其进行排序，接下来将排序后的数组中的数字按照从小到大的顺序交替地分配给 $num1$ 和 $num2$，最后返回 $num1$ 和 $num2$ 的和即可。

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

func splitNum(num int) int {
	s := []byte(strconv.Itoa(num))
	sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
	ans := [2]int{}
	for i, c := range s {
		ans[i&1] = ans[i&1]*10 + int(c-'0')
	}
	return ans[0] + ans[1]
}

力扣原题 · Doocs 题解来源

2587. 重排数组以得到最大前缀分数

中等1 种解法

标签：贪心、数组、前缀和、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。

令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。nums 的 分数 是 prefix 数组中正整数的个数。

返回可以得到的最大分数。

 

示例 1：

输入：nums = [2,-1,0,1,-3,3,-3]
输出：6
解释：数组重排为 nums = [2,3,1,-1,-3,0,-3] 。
prefix = [2,5,6,5,2,2,-1] ，分数为 6 。
可以证明 6 是能够得到的最大分数。

示例 2：

输入：nums = [-2,-3,0]
输出：0
解释：不管怎么重排数组得到的分数都是 0 。

 

提示：

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

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

思考

重排数组，使严格为正的前缀和尽量多。正数应尽早出现，负数尽量靠后，故降序排列。

累加前缀，一旦和落入非正，后面只会更小，此前的个数即为答案；全程为正则答案是 $n$。

要使得前缀和数组中正整数的个数最多，就要使得前缀和数组中的元素尽可能大，即尽可能多的正整数相加。因此，我们可以将数组 $nums$ 降序排序，然后遍历数组，维护前缀和 $s$，如果 $s\le 0$，则说明当前位置以及之后的位置都不可能再有正整数，因此直接返回当前位置即可。

否则，遍历结束后，返回数组长度。

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

func maxScore(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	s := 0
	for i := range nums {
		s += nums[n-i-1]
		if s <= 0 {
			return i
		}
	}
	return n
}

力扣原题 · Doocs 题解来源

2589. 完成所有任务的最少时间

困难1 种解法

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

题目、示例与约束

你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。

当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。

请你返回完成所有任务的情况下，电脑最少需要运行多少秒。

 

示例 1：

输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
输出：2
解释：
- 第一个任务在闭区间 [2, 2] 运行。
- 第二个任务在闭区间 [5, 5] 运行。
- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
电脑总共运行 2 个整数时间点。

示例 2：

输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
输出：4
解释：
- 第一个任务在闭区间 [2, 3] 运行
- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
- 第三个任务在闭区间 [5, 6] 运行。
电脑总共运行 4 个整数时间点。

 

提示：

• 1 <= tasks.length <= 2000
• tasks[i].length == 3
• 1 <= starti, endi <= 2000
• 1 <= durationi <= endi - starti + 1

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

思考

每个任务须在闭区间内占用 $\mathit{\text{duration}}$ 个整点，电脑同时只跑一个任务，求最少开机时长。时间轴只有 $2000$，但任务组合很多。

按结束时间排序后，尽量占用区间最右端尚未使用的时刻，这些点更可能被后续更晚结束的任务共享。先扣除区间内已占用的点，再从右往左补足差额。

我们观察发现，题目相当于在每一个区间 $[start,..,end]$ 中，选择 $duration$ 个整数时间点，使得总共选择的整数时间点最少。

因此，我们可以先对 $tasks$ 按照结束时间 $end$ 从小到大排序。然后贪心地进行选择，对于每一个任务，我们从结束时间 $end$ 开始，从后往前选择尽可能靠后的点，这样这些点更有可能被后面的任务重复利用。

我们在实现上，可以用一个长度为 $2010$ 的数组 $vis$ 记录每个时间点是否被选择过。然后对于每一个任务，我们先统计 $[start,..,end]$ 区间内已经被选择过的点的个数 $cnt$，然后从后往前选择 $duration-cnt$ 个点，同时记录选择的点的个数 $ans$ 以及更新 $vis$ 数组。

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

时间复杂度 $O(n\times \log n+n\times m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为 $tasks$ 的长度和 $vis$ 数组的长度。本题中 $m=2010$。

func findMinimumTime(tasks [][]int) (ans int) {
	sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
	vis := [2010]int{}
	for _, task := range tasks {
		start, end, duration := task[0], task[1], task[2]
		for _, x := range vis[start : end+1] {
			duration -= x
		}
		for i := end; i >= start && duration > 0; i-- {
			if vis[i] == 0 {
				vis[i] = 1
				duration--
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2591. 将钱分给最多的儿童

简单1 种解法

标签：贪心、数学

题目、示例与约束

给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。

你需要按照如下规则分配：

• 所有的钱都必须被分配。
• 每个儿童至少获得 1 美元。
• 没有人获得 4 美元。

请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美元。如果没有任何分配方案，返回 -1 。

 

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。

示例 2：

输入：money = 16, children = 2
输出：2
解释：每个儿童都可以获得 8 美元。

 

提示：

• 1 <= money <= 200
• 2 <= children <= 30

方法一：分类讨论 · Go 实现

思考

每人至少 $1$ 美元，得到 $8$ 美元的人数尽量多，且不能有人恰好得到 $4$ 美元。钱不够每人 $1$ 美元则无解。

总额超过 $8\times \mathit{\text{children}}$ 时必须有人多于 $8$，最多只能让 $\mathit{\text{children}}-1$ 人拿满 $8$。总额恰为 $8n-4$ 时，若已有 $n-1$ 人拿 $8$，剩下的人会拿到 $4$，故再少一人。其余情形每人先拿 $1$，剩余每 $7$ 美元可多造一个 $8$，即 $\lfloor (\mathit{\text{money}}-\mathit{\text{children}})/7\rfloor$。

如果 $money<children$，那么一定存在儿童没有分到钱，返回 $-1$。

如果 $money>8\times children$，那么有 $children-1$ 个儿童获得了 $8$ 美元，剩下的一个儿童获得了 $money-8\times (children-1)$ 美元，返回 $children-1$。

如果 $money=8\times children-4$，那么有 $children-2$ 个儿童获得了 $8$ 美元，剩下的两个儿童分摊剩下的 $12$ 美元（只要不是 $4$, $8$ 美元就行），返回 $children-2$。

如果，我们假设有 $x$ 个儿童获得了 $8$ 美元，那么剩下的钱为 $money-8\times x$，只要保证大于等于剩下的儿童数 $children-x$，就可以满足题意。因此，我们只需要求出 $x$ 的最大值，即为答案。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

func distMoney(money int, children int) int {
	if money < children {
		return -1
	}
	if money > 8*children {
		return children - 1
	}
	if money == 8*children-4 {
		return children - 2
	}
	// money-8x >= children-x, x <= (money-children)/7
	return (money - children) / 7
}

力扣原题 · Doocs 题解来源

2592. 最大化数组的伟大值

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。

定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。

请你返回重新排列 nums 后的 最大 伟大值。

 

示例 1：

输入：nums = [1,3,5,2,1,3,1]
输出：4
解释：一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。
在下标为 0, 1, 3 和 4 处，都有 perm[i] > nums[i] 。因此我们返回 4 。

示例 2：

输入：nums = [1,2,3,4]
输出：3
解释：最优排列为 [2,3,4,1] 。
在下标为 0, 1 和 2 处，都有 perm[i] > nums[i] 。因此我们返回 3 。

 

提示：

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

方法一：贪心 · Go 实现

思考

排列 $perm$ 的伟大程度是 $perm[i]>nums[i]$ 的位置数，求最大值。这是两侧多重集相同的配对，应让较大值去压过尽可能多的较小数。

排序后用双指针：从左到右扫较大候选 $x$，若它严格大于当前未被压过的 $nums[i]$ 则配对成功。能压过的个数即答案。

我们可以先将数组 $nums$ 进行排序。

接下来定义一个指针 $i$，初始时指向数组 $nums$ 的第一个元素。然后遍历数组 $nums$，对于遍历到的每个元素 $x$，如果 $x$ 大于 $nums[i]$，则将指针 $i$ 向右移动一位。

最后返回指针 $i$ 的值即可。

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

func maximizeGreatness(nums []int) int {
	sort.Ints(nums)
	i := 0
	for _, x := range nums {
		if x > nums[i] {
			i++
		}
	}
	return i
}

力扣原题 · Doocs 题解来源

2598. 执行操作后的最大 MEX

中等1 种解法

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

题目、示例与约束

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

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

 

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

 

提示：

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

方法一：计数 · Go 实现

思考

每个数可加减任意次 $\mathit{\text{value}}$，即可以变成与它同余的任意整数。求操作后能达到的最小 $mex$。

同余类 $r$ 能提供 $r,r+\mathit{\text{value}},r+2\mathit{\text{value}},\dots$。从 $0$ 起依次需要余数 $0,1,\dots$，某余数用尽时该整数即为 $mex$。统计各余数个数后线性扫描即可。

我们用哈希表 $\mathit{\text{cnt}}$ 统计数组中每个数对 $\mathit{\text{value}}$ 取模后的余数的个数。

然后从 $0$ 开始遍历，对于当前遍历到的数 $i$，如果 $\mathit{\text{cnt}}[imod\mathit{\text{value}}]$ 为 $0$，说明数组中不存在一个数对 $\mathit{\text{value}}$ 取模后的余数为 $i$，那么 $i$ 就是数组的 MEX，直接返回即可。否则，将 $\mathit{\text{cnt}}[imod\mathit{\text{value}}]$ 减 $1$，继续遍历。

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

func findSmallestInteger(nums []int, value int) int {
	cnt := make([]int, value)
	for _, x := range nums {
		cnt[(x%value+value)%value]++
	}
	for i := 0; ; i++ {
		if cnt[i%value] == 0 {
			return i
		}
		cnt[i%value]--
	}
}

力扣原题 · Doocs 题解来源

2599. 使前缀和数组非负 🔒

中等1 种解法

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

题目、示例与约束

给定一个 下标从0开始 的整数数组 nums 。你可以任意多次执行以下操作：

• 从 nums 中选择任意一个元素，并将其放到 nums 的末尾。

nums 的前缀和数组是一个与 nums 长度相同的数组 prefix ，其中 prefix[i] 是所有整数 nums[j]（其中 j 在包括区间 [0，i] 内）的总和。

返回使前缀和数组不包含负整数的最小操作次数。测试用例的生成方式保证始终可以使前缀和数组非负。

 

示例 1 ：

输入：nums = [2,3,-5,4]
输出：0
解释：我们不需要执行任何操作。
给定数组为 [2, 3, -5, 4]，它的前缀和数组是 [2, 5, 0, 4]。

示例 2 ：

输入：nums = [3,-5,-2,6]
输出：1
解释：我们可以对索引为1的元素执行一次操作。
操作后的数组为 [3, -2, 6, -5]，它的前缀和数组是 [3, 1, 7, 2]。

 

提示：

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

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

思考

每次可把一个元素移到数组末尾，要使每个前缀和都不为负，求最少移动次数。移动会改变后续前缀，枚举移动集合不可行。

从左到右累加，负数才可能把前缀拉负。当前和一旦为负，应移走此前仍留在原位的最小负数，这样用最少次数让和回到非负。小根堆保存这些负数，弹出时从和里减去（相当于移走）并计数。

我们用变量 $s$ 记录当前数组的前缀和。

遍历数组 $nums$，将当前元素 $x$ 加入前缀和 $s$ 中，如果 $x$ 为负数，则将 $x$ 加入小根堆中。如果此时 $s$ 为负数，我们贪心地取出最小的负数，将其从 $s$ 中减去，同时将答案加一。最终返回答案即可。

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

func makePrefSumNonNegative(nums []int) (ans int) {
	pq := hp{}
	s := 0
	for _, x := range nums {
		s += x
		if x < 0 {
			heap.Push(&pq, x)
		}
		for s < 0 {
			s -= heap.Pop(&pq).(int)
			ans++
		}
	}
	return 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 题解来源

2600. K 件物品的最大和

简单1 种解法

标签：贪心、数学

题目、示例与约束

袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。

给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。

袋子最初包含：

• numOnes 件标记为 1 的物品。
• numZeros 件标记为 0 的物品。
• numNegOnes 件标记为 -1 的物品。

现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。

 

示例 1：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 2 件标记为 1 的物品，得到的数字之和为 2 。
可以证明 2 是所有可行方案中的最大值。

示例 2：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出：3
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 3 件标记为 1 的物品，1 件标记为 0 的物品，得到的数字之和为 3 。
可以证明 3 是所有可行方案中的最大值。

 

提示：

• 0 <= numOnes, numZeros, numNegOnes <= 50
• 0 <= k <= numOnes + numZeros + numNegOnes

方法一：贪心 · Go 实现

思考

三种标记的取值固定，若枚举取了几件 $1$、几件 $0$、几件 $-1$，组合数随 $k$ 线性增长。题目要求恰好取 $k$ 件且和最大，而 $k$ 与各计数均不超过 $50$，穷举可行，但并无必要。

和由 $1$、 $0$、 $-1$ 线性叠加，多取一件 $1$ 严格优于多取一件 $0$，多取一件 $0$ 又优于多取一件 $-1$。因此最优策略唯一：先取尽 $1$，不足再取 $0$，仍不足才取 $-1$。

比较 $k$ 与 $\mathit{\text{numOnes}}$、 $\mathit{\text{numZeros}}$ 即可在常数时间内落到上述三段之一，无需真正构造选取方案。

根据题目描述，我们应该尽可能多地取标记为 $1$ 的物品，然后取标记为 $0$ 的物品，最后取标记为 $-1$ 的物品。

因此：

• 如果袋子中的物品标记为 $1$ 的数量大于等于 $k$，那么取 $k$ 件物品，数字之和为 $k$；
• 如果袋子中的物品标记为 $1$ 的数量小于 $k$，那么取 $\mathit{\text{numOnes}}$ 件物品，数字之和为 $\mathit{\text{numOnes}}$；如果标记为 $0$ 的物品数量大于等于 $k-\mathit{\text{numOnes}}$，那么再取 $k-\mathit{\text{numOnes}}$ 件物品，数字之和还是 $\mathit{\text{numOnes}}$；
• 否则，我们再从标记为 $-1$ 的物品中取 $k-\mathit{\text{numOnes}}-\mathit{\text{numZeros}}$ 件物品，数字之和为 $\mathit{\text{numOnes}}-(k-\mathit{\text{numOnes}}-\mathit{\text{numZeros}})$。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

func kItemsWithMaximumSum(numOnes int, numZeros int, numNegOnes int, k int) int {
	if numOnes >= k {
		return k
	}
	if numZeros >= k-numOnes {
		return numOnes
	}
	return numOnes - (k - numOnes - numZeros)
}

力扣原题 · Doocs 题解来源

2601. 质数减法运算

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。

你可以执行无限次下述运算：

• 选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。

如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。

严格递增数组 中的每个元素都严格大于其前面的元素。

 

示例 1：

输入：nums = [4,9,6,10]
输出：true
解释：
在第一次运算中：选择 i = 0 和 p = 3 ，然后从 nums[0] 减去 3 ，nums 变为 [1,9,6,10] 。
在第二次运算中：选择 i = 1 和 p = 7 ，然后从 nums[1] 减去 7 ，nums 变为 [1,2,6,10] 。
第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。

示例 2：

输入：nums = [6,8,11,12]
输出：true
解释：nums 从一开始就按严格递增顺序排序，因此不需要执行任何运算。

示例 3：

输入：nums = [5,8,3]
输出：false
解释：可以证明，执行运算无法使 nums 按严格递增顺序排序，因此答案是 false 。

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

方法一：预处理质数 + 二分查找 · Go 实现

思考

每个位置至多减一次质数，且须使整个数组严格递增。若从左向右贪心，当前值压得过低可能让后续无法衔接；若对每个位置枚举全部质数， $n\le 1000$ 且值域不超过 $1000$，时间尚可，但需要确定扫描方向。

注意到右端 $nums[n-1]$ 越大越宽松，因此从右往左处理：当 $nums[i]\ge nums[i+1]$ 时，必须减去一个严格大于 $nums[i]-nums[i+1]$ 且小于 $nums[i]$ 的质数，并取其中最小者，以免过度压缩左侧空间。

为此先筛出 $1000$ 以内质数表 $p$，再在 $p$ 上二分定位满足下界的最小质数。若无此类质数则不可行。

我们先预处理得到 $1000$ 以内的所有质数，记录在数组 $p$ 中。

对于数组 $nums$ 中的每个元素 $nums[i]$，我们需要找到一个质数 $p[j]$，使得 p[j] \gt nums[i] - nums[i + 1]，并且 $p[j]$ 尽可能小。如果找不到这样的质数，说明无法通过减法运算使得 $nums$ 严格递增，返回 false。如果找到了这样的质数，我们就将 $nums[i]$ 减去 $p[j]$，并继续处理下一个元素。

如果 $nums$ 中的所有元素都处理完了，说明可以通过减法运算使得 $nums$ 严格递增，返回 true。

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

func primeSubOperation(nums []int) bool {
	p := []int{}
	for i := 2; i <= 1000; i++ {
		ok := true
		for _, j := range p {
			if i%j == 0 {
				ok = false
				break
			}
		}
		if ok {
			p = append(p, i)
		}
	}
	for i := len(nums) - 2; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			continue
		}
		j := sort.SearchInts(p, nums[i]-nums[i+1]+1)
		if j == len(p) || p[j] >= nums[i] {
			return false
		}
		nums[i] -= p[j]
	}
	return true
}

力扣原题 · Doocs 题解来源

2607. 使子数组元素和相等

中等1 种解法

标签：贪心、数组、数学、数论、排序

题目、示例与约束

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

• 选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

 

示例 1：

输入：arr = [1,4,1,3], k = 2
输出：1
解释：在下标为 1 的元素那里执行一次运算，使其等于 3 。
执行运算后，数组变为 [1,3,1,3] 。
- 0 处起始的子数组为 [1, 3] ，元素总和为 4 
- 1 处起始的子数组为 [3, 1] ，元素总和为 4 
- 2 处起始的子数组为 [1, 3] ，元素总和为 4 
- 3 处起始的子数组为 [3, 1] ，元素总和为 4 

示例 2：

输入：arr = [2,5,5,7], k = 3
输出：5
解释：在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。
执行运算后，数组变为 [5,5,5,5] 。
- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15

 

提示：

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

方法一：数学（裴蜀定理） + 中位数贪心 · Go 实现

思考

相邻长度为 $k$ 的子数组和相等，化简后得到 $ar{r}_i=ar{r}_{i+k}$。数组又是环状的，故间隔 $k$ 与间隔 $n$ 的完全剩余系必须取同一值。

由裴蜀定理，这些下标按 $gcd(n,k)$ 分成若干独立链。链内元素须改成同一个数，操作次数为到某目标的绝对差之和，中位数使其最小。

因此对每个剩余类排序后取中位数，累加偏差。

题目要求每个长度为 $k$ 的子数组的元素总和相等，那么有以下等式成立：

$$ar{r}_i+ar{r}_{i+1}+\cdots +ar{r}_{i+k-1}=ar{r}_{i+1}+ar{r}_{i+2}+\cdots +ar{r}_{i+k}$$

化简得：

$$ar{r}_i=ar{r}_{i+k}$$

也即是说，数组 $arr$ 有一个大小为 $k$ 的循环节，而由于数组 $arr$ 是一个循环数组，那么数组 $arr$ 也有一个长度为 $n$ 的循环节。换句话说，数组 $arr$ 上间隔为 $k$，以及间隔为 $n$ 的元素均相等。即有：

$$ar{r}_i=ar{r}_{i+k\times x+n\times y}$$

根据裴蜀定理，有 $a\times x+b\times y=gcd(a,b)$，因此，有：

$$ar{r}_i=ar{r}_{i+k\times x+n\times y}=ar{r}_{i+gcd(k,n)}$$

因此，数组 $arr$ 上的元素可以分为 $gcd(k,n)$ 组，每组的元素间隔为 $gcd(k,n)$，且每一组中的所有元素均相等。对于每一组，我们可以将其元素按照大小排序，然后取中位数，即可将该组中的所有元素变为中位数。对于所有组，我们将其中位数之差的绝对值求和，即为答案。

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

func makeSubKSumEqual(arr []int, k int) (ans int64) {
	n := len(arr)
	g := gcd(n, k)
	for i := 0; i < g; i++ {
		t := []int{}
		for j := i; j < n; j += g {
			t = append(t, arr[j])
		}
		sort.Ints(t)
		mid := t[len(t)/2]
		for _, x := range t {
			ans += int64(abs(x - mid))
		}
	}
	return
}

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

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

2611. 老鼠和奶酪

中等2 种解法

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

题目、示例与约束

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

• 如果第一只老鼠吃掉，则得分为 reward1[i] 。
• 如果第二只老鼠吃掉，则得分为 reward2[i] 。

给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

 

示例 1：

输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。

示例 2：

输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。

 

提示：

• 1 <= n == reward1.length == reward2.length <= 105
• 1 <= reward1[i], reward2[i] <= 1000
• 0 <= k <= n

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

思考

第一只老鼠恰吃 $k$ 块，其余归第二只。枚举子集 $C(n,k)$ 在 $n\le {10}^5$ 下不可行。

先把全部奶酪记给第二只，再挑选 $k$ 块改给第一只，得分变化为 $reward1[i]-reward2[i]$。变化量越大越应改分。

按下标差降序排序，前 $k$ 块用 $reward1$，其余用 $reward2$。

我们可以先将所有奶酪分给第二只老鼠，因此初始得分为 $\sum _{i=0}^{n-1}reward2[i]$。

接下来，考虑将其中 $k$ 块奶酪分给第一只老鼠，那么我们应该如何选择这 $k$ 块奶酪呢？显然，将第 $i$ 块奶酪从第二只老鼠分给第一只老鼠，得分的变化量为 $reward1[i]-reward2[i]$，我们希望这个变化量尽可能大，这样才能使得总得分最大。

因此，我们将奶酪按照 $reward1[i]-reward2[i]$ 从大到小排序，前 $k$ 块奶酪由第一只老鼠吃掉，剩下的奶酪由第二只老鼠吃掉，即可得到最大得分。也即是说，我们将初始得分加上 $\sum _{i=0}^{k-1}(reward1[i]-reward2[i])$ 即可。

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

相似题目：

• 1029. 两地调度

func miceAndCheese(reward1 []int, reward2 []int, k int) (ans int) {
	n := len(reward1)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool {
		i, j = idx[i], idx[j]
		return reward1[j]-reward2[j] < reward1[i]-reward2[i]
	})
	for i := 0; i < k; i++ {
		ans += reward1[idx[i]]
	}
	for i := k; i < n; i++ {
		ans += reward2[idx[i]]
	}
	return
}

方法二 · Go 实现

思考

方法一另开下标数组排序。把差值写回 $reward1$ 再原地降序，答案为 $\sum reward2$ 加上最大的 $k$ 个差值，省去下标映射。

func miceAndCheese(reward1 []int, reward2 []int, k int) (ans int) {
	for i, x := range reward2 {
		ans += x
		reward1[i] -= x
	}
	sort.Ints(reward1)
	n := len(reward1)
	for i := 0; i < k; i++ {
		ans += reward1[n-i-1]
	}
	return
}

力扣原题 · Doocs 题解来源

2656. K 个元素的最大和

简单1 种解法

标签：贪心、数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：

1. 从 nums 中选择一个元素 m 。
2. 将选中的元素 m 从数组中删除。
3. 将新元素 m + 1 添加到数组中。
4. 你的得分增加 m 。

请你返回执行以上操作恰好 k 次后的最大得分。

 

示例 1：

输入：nums = [1,2,3,4,5], k = 3
输出：18
解释：我们需要从 nums 中恰好选择 3 个元素并最大化得分。
第一次选择 5 。和为 5 ，nums = [1,2,3,4,6] 。
第二次选择 6 。和为 6 ，nums = [1,2,3,4,7] 。
第三次选择 7 。和为 5 + 6 + 7 = 18 ，nums = [1,2,3,4,8] 。
所以我们返回 18 。
18 是可以得到的最大答案。

示例 2：

输入：nums = [5,5,5], k = 2
输出：11
解释：我们需要从 nums 中恰好选择 2 个元素并最大化得分。
第一次选择 5 。和为 5 ，nums = [5,5,6] 。
第二次选择 6 。和为 6 ，nums = [5,5,7] 。
所以我们返回 11 。
11 是可以得到的最大答案。

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

方法一：贪心 + 数学 · Go 实现

思考

每次取当前最大并把它加 $1$ 放回，做 $k$ 次。若真的模拟插入， $k\le 100$ 尚可，但最优总是反复操作全局最大 $x$。

得分是 $x+(x+1)+\cdots +(x+k-1)=kx+k(k-1)/2$，一次求 $max$ 即可。

我们注意到，要使得最终的得分最大，我们应该尽可能地使得每次选择的元素最大。因此，我们第一次选择数组中的最大元素 $x$，第二次选择 $x+1$，第三次选择 $x+2$，以此类推，直到第 $k$ 次选择 $x+k-1$。这样的选择方式可以保证每次选择的元素都是当前数组中的最大值，因此最终的得分也是最大的。答案即为 $k$ 个 $x$ 的和加上 $0+1+2+\cdots +(k-1)$，即 $k\times x+(k-1)\times k/2$。

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

func maximizeSum(nums []int, k int) int {
	x := slices.Max(nums)
	return k*x + k*(k-1)/2
}

力扣原题 · Doocs 题解来源

2663. 字典序最小的美丽字符串

困难1 种解法

标签：贪心、字符串

题目、示例与约束

如果一个字符串满足以下条件，则称其为 美丽字符串 ：

• 它由英语小写字母表的前 k 个字母组成。
• 它不包含任何长度为 2 或更长的回文子字符串。

给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。

请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。

• 例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。

 

示例 1：

输入：s = "abcz", k = 26
输出："abda"
解释：字符串 "abda" 既是美丽字符串，又满足字典序大于 "abcz" 。
可以证明不存在字符串同时满足字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。

示例 2：

输入：s = "dc", k = 4
输出：""
解释：可以证明，不存在既是美丽字符串，又字典序大于 "dc" 的字符串。

 

提示：

• 1 <= n == s.length <= 105
• 4 <= k <= 26
• s 是一个美丽字符串

方法一：贪心 · Go 实现

思考

美丽串不含长 $\ge 2$ 的回文，即每位与前两位都不同。要找比 $s$ 大的最小美丽串。从左修改会牵动后缀，字典序最小应尽量改最右侧。

自右向左找第一位还能升格到某个合法更大字母；其后各位放尽可能小的合法字母。若无人可升格则无解。字母表大小 $k\le 26$， $n\le {10}^5$ 下每位尝试常数次。

我们可以发现，一个长度为 $2$ 的回文字符串，其相邻两个字符一定相同；而一个长度为 $3$ 的回文字符串，其首尾两个字符一定相同。因此，一个美丽字符串不包含任何长度为 $2$ 或更长的回文子字符串，意味着该字符串的每个字符与其相邻的前两个字符都不相同。

我们可以贪心地从字符串的最后一个下标开始往前查找，找到一个下标 $i$，使得下标 $i$ 处的字符可以被替换为一个比其稍大的字符，同时保证其与其相邻的前两个字符都不相同的字符 $c$。

• 若找到了这样的下标 $i$，那么我们将 $s[i]$ 替换为 $c$，并将 $s[i+1]$ 到 $s[n-1]$ 的字符依次替换为字典序尽可能小的、不与前面相邻两个字符相同的、且在字母表前 $k$ 个字符中的字符，替换完成后，我们就得到了一个字典序最小的且大于 $s$ 的美丽字符串。
• 若找不到这样的下标 $i$，那么我们就无法构造出字典序大于 $s$ 的美丽字符串，因此返回空字符串。

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

func smallestBeautifulString(s string, k int) string {
	cs := []byte(s)
	n := len(cs)
	for i := n - 1; i >= 0; i-- {
		p := int(cs[i] - 'a' + 1)
		for j := p; j < k; j++ {
			c := byte('a' + j)
			if (i > 0 && cs[i-1] == c) || (i > 1 && cs[i-2] == c) {
				continue
			}
			cs[i] = c
			for l := i + 1; l < n; l++ {
				for m := 0; m < k; m++ {
					c = byte('a' + m)
					if (l > 0 && cs[l-1] == c) || (l > 1 && cs[l-2] == c) {
						continue
					}
					cs[l] = c
					break
				}
			}
			return string(cs)
		}
	}
	return ""
}

力扣原题 · Doocs 题解来源

2680. 最大或值

中等1 种解法

标签：贪心、位运算、数组、前缀和

题目、示例与约束

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

 

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

 

提示：

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

方法一：贪心 + 预处理 · Go 实现

思考

可把某数左移至多 $k$ 次，使全体按位或最大。移位分散到多个数会把高位拆开，不如把 $k$ 次全给同一个数。

枚举被放大的 $nums[i]$ 时，其余部分是其前缀或与后缀或，预处理 $suf$ 后一次扫描即可。

我们注意到，为了使得答案最大，我们应该将 $k$ 次乘 $2$ 作用于同一个数。

我们先预处理出数组 $nums$ 的后缀或值数组 $suf$，其中 $suf[i]$ 表示 $nums[i],nums[i+1],\cdots ,nums[n-1]$ 的按位或值。

接下来，我们从左到右遍历数组 $nums$，同时维护当前的前缀或值 $pre$。对于当前遍历到的位置 $i$，我们将 $nums[i]$ 乘 $2$ 的 $k$ 次方，即 $nums[i]\times 2^k$，与 $pre$ 进行按位或运算，得到的结果再与 $suf[i+1]$ 进行按位或运算，即可得到以 $nums[i]$ 为最后一个数的最大或值。枚举所有的 $i$，即可得到答案。

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

func maximumOr(nums []int, k int) int64 {
	n := len(nums)
	suf := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		suf[i] = suf[i+1] | nums[i]
	}
	ans, pre := 0, 0
	for i, x := range nums {
		ans = max(ans, pre|(nums[i]<<k)|suf[i+1])
		pre |= x
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2697. 字典序最小回文串

简单1 种解法

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

题目、示例与约束

给你一个由 小写英文字母 组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 替换  s 中的一个字符。

请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小 的方案。

对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。

返回最终的回文字符串。

 

示例 1：

输入：s = "egcfe"
输出："efcfe"
解释：将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。

示例 2：

输入：s = "abcd"
输出："abba"
解释：将 "abcd" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。

示例 3：

输入：s = "seven"
输出："neven"
解释：将 "seven" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "neven" 。

 

提示：

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

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

思考

只能把字母改小，且最终须为回文。两端应对称，字典序最小应取两端中的较小者同时写入。 $n\le {10}^5$，双指针一次扫描即可，无需枚举改哪些位。

我们用两个指针 $i$ 和 $j$ 分别指向字符串的首尾，初始时 $i=0$, $j=n-1$。

接下来，我们每一次都贪心地将 $s[i]$ 和 $s[j]$ 修改为它们中的较小值，使得它们相等。然后将 $i$ 向后移动一位，将 $j$ 向前移动一位，继续进行这一过程，直到 $i\ge j$ 为止。此时，我们就得到了最小的回文串。

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

func makeSmallestPalindrome(s string) string {
	cs := []byte(s)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		cs[i] = min(cs[i], cs[j])
		cs[j] = cs[i]
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

2706. 购买两块巧克力

简单2 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。

你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。

请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。

 

示例 1：

输入：prices = [1,2,2], money = 3
输出：0
解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。

示例 2：

输入：prices = [3,2,3], money = 3
输出：3
解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。

 

提示：

• 2 <= prices.length <= 50
• 1 <= prices[i] <= 100
• 1 <= money <= 100

方法一：排序 · Go 实现

思考

必须恰好买两块且花费不超过 $money$，并最大化剩余。枚举所有无序对在 $n\le 50$ 下可通过，但答案只取决于最便宜的两块。

将价格排序后取前两项之和 $cost$，若 $cost>money$ 则无法购买，否则剩余为 $money-cost$。

我们可以将巧克力的价格从小到大排序，然后取前两个价格相加，就是我们购买两块巧克力的最小花费 $cost$。如果这个花费大于我们拥有的钱数，那么我们就返回 money，否则返回 money - cost。

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

func buyChoco(prices []int, money int) int {
	sort.Ints(prices)
	cost := prices[0] + prices[1]
	if money < cost {
		return money
	}
	return money - cost
}

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

思考

排序付出 $O(n\log n)$，而我们只需要两个最小值。一次扫描维护当前最小与次小，即可在线性时间内得到同样的 $cost$。

我们可以在一次遍历中找到最小的两个价格，然后计算花费。

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

func buyChoco(prices []int, money int) int {
	a, b := 1001, 1001
	for _, x := range prices {
		if x < a {
			a, b = x, a
		} else if x < b {
			b = x
		}
	}
	cost := a + b
	if money < cost {
		return money
	}
	return money - cost
}

力扣原题 · Doocs 题解来源

2734. 执行子串操作后的字典序最小字符串

中等1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

• 选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。

返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。

子字符串 是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果  x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。

 

示例 1：

输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 
可以证明最终得到的字符串是字典序最小的。

示例 2：

输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

示例 3：

输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

 

提示：

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

方法一：贪心 · Go 实现

思考

必须对一段连续子串把每个字母减一（ $a$ 变为 $z$），且只能操作一次，求字典序最小结果。枚举所有子串在 $n\le {10}^5$ 时不可行。

$a$ 减一会变成最大的 $z$，应尽量避开。从左侧第一段非 $a$ 开始减到下一处 $a$ 之前，可使最早的位置下降。整串皆 $a$ 时题目仍要求操作一次，只能把末位改成 $z$。

我们可以从左到右遍历字符串 $s$，找到第一个不是 'a' 的字符所在的位置 $i$，然后找到从 $i$ 开始的第一个 'a' 字符所在的位置 $j$，将 $s[i:j]$ 中的字符都减一，最后返回处理后的字符串即可。

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

func smallestString(s string) string {
	n := len(s)
	i := 0
	for i < n && s[i] == 'a' {
		i++
	}
	cs := []byte(s)
	if i == n {
		cs[n-1] = 'z'
		return string(cs)
	}
	j := i
	for j < n && cs[j] != 'a' {
		cs[j] = cs[j] - 1
		j++
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

2789. 合并后数组中的最大元素

中等1 种解法

标签：贪心、数组

题目、示例与约束

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

你可以在数组上执行下述操作 任意 次：

• 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的下标 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

 

示例 1：

输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
最终数组中只有一个元素，即 11 。

 

提示：

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

方法一：倒序合并 · Go 实现

思考

仅当 $nums[i]\le nums[i+1]$ 时才能把二者合成右侧之和，求操作后可能出现的最大元素。从左合并会过早用掉较小的数，挡住后面的连锁。

从右向左：若 $nums[i]\le nums[i+1]$ 就原地累加到 $nums[i]$，相当于把右侧已经尽量大的段并进来。最后数组中的最大值即为答案。

根据题目描述，为了最大化合并后的数组中的最大元素，我们应该先合并右侧的元素，使得右侧的元素尽可能大，从而尽可能多地执行合并操作，最终得到最大的元素。

因此，我们可以从右向左遍历数组，对于每个位置 $i$，其中 $i\in [0,n-2]$，如果 $nums[i]\le nums[i+1]$，我们就将 $nums[i]$ 更新为 $nums[i]+nums[i+1]$。这样做，相当于将 $nums[i]$ 与 $nums[i+1]$ 合并，并且删掉 $nums[i]$。

最终，数组中的最大元素就是合并后的数组中的最大元素。

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

func maxArrayValue(nums []int) int64 {
	n := len(nums)
	ans, t := nums[n-1], nums[n-1]
	for i := n - 2; i >= 0; i-- {
		if nums[i] <= t {
			t += nums[i]
		} else {
			t = nums[i]
		}
		ans = max(ans, t)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2790. 长度递增组的最大数目

困难1 种解法

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

题目、示例与约束

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：

• 每个组必须由 不同 的数字组成，也就是说，单个组内不能存在重复的数字。
• 每个组（除了第一个）的长度必须 严格大于 前一个组。

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

 

示例 1：

输入：usageLimits = [1,2,5]
输出：3
解释：在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。 
可以证明能够创建的最大组数是 3 。 
所以，输出是 3 。 

示例 2：

输入：usageLimits = [2,1,2]
输出：2
解释：在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [0] 。 
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。 
所以，输出是 2 。 

示例 3：

输入：usageLimits = [1,1]
输出：1
解释：在这个示例中，我们可以使用 0 和 1 至多 1 次。 
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。 
所以，输出是 1 。 

 

提示：

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

方法一：贪心 · Go 实现

思考

第 $k$ 组需要 $k$ 个两两不同的数，且每个数 $i$ 至多用 $usageLimits[i]$ 次，求最多组数。直接枚举组数再分配额度需要匹配。

限额升序后从左消耗：累计剩余额度一旦够开第 $k+1$ 组就开一组并扣掉 $k+1$，余量滚入下一个限额。贪心保证先用掉较小配额，组数尽量多。

将限额从小到大排序后依次累加。每多出一个可用额度，就尝试多开一组；能开则把该组消耗从累计中扣掉。最终组数即为答案。

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

func maxIncreasingGroups(usageLimits []int) int {
	sort.Ints(usageLimits)
	s, k := 0, 0
	for _, x := range usageLimits {
		s += x
		if s > k {
			k++
			s -= k
		}
	}
	return k
}

力扣原题 · Doocs 题解来源

2800. 包含三个字符串的最短字符串

中等2 种解法

标签：贪心、字符串、枚举

题目、示例与约束

给你三个字符串 a ，b 和 c ， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。

如果有多个这样的字符串，请你返回 字典序最小 的一个。

请你返回满足题目要求的字符串。

注意：

• 两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母 靠前 ，那么字符串 a 比字符串 b 字典序小 。
• 子字符串 是一个字符串中一段连续的字符序列。

 

示例 1：

输入：a = "abc", b = "bca", c = "aaa"
输出："aaabca"
解释：字符串 "aaabca" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且"aaabca" 是字典序最小的一个。

示例 2：

输入：a = "ab", b = "ba", c = "aba"
输出："aba"
解释：字符串 "aba" 包含所有三个字符串：a = ans[0..1] ，b = ans[1..2] ，c = ans[0..2] 。由于 c 的长度为 3 ，结果字符串的长度至少为 3 。"aba" 是字典序最小的一个。

 

提示：

• 1 <= a.length, b.length, c.length <= 100
• a ，b ，c 只包含小写英文字母。

方法一：枚举 · Go 实现

思考

三个字符串长度均不超过 $100$，排列只有 $6$ 种，因而可以穷尽所有拼接顺序。答案须同时最短且字典序最小，包含关系与首尾重叠都会改变候选。若某一串已是另一串的子串，则不必再单独拼接；否则最优超串对应某一种排列下的依次合并。函数 $f$ 先处理包含，再从大到小检查后缀与前缀的重合，并按长度与字典序维护最优解。

我们枚举三个字符串的所有排列，然后对于每个排列，对三个字符串进行合并，找到最短的且字典序最小的字符串。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是三个字符串的长度的最大值。

func minimumString(a string, b string, c string) string {
	f := func(s, t string) string {
		if strings.Contains(s, t) {
			return s
		}
		if strings.Contains(t, s) {
			return t
		}
		m, n := len(s), len(t)
		for i := min(m, n); i > 0; i-- {
			if s[m-i:] == t[:i] {
				return s + t[i:]
			}
		}
		return s + t
	}
	s := [3]string{a, b, c}
	ans := ""
	for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
		i, j, k := p[0], p[1], p[2]
		t := f(f(s[i], s[j]), s[k])
		if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
			ans = t
		}
	}
	return ans
}

方法二：枚举 + KMP · Go 实现

思考

方法一在合并时对重叠长度做线性扫描，单次合并达到 $O(n^2)$。将 $t\mathrm{\#}s$ 做 KMP 前缀函数后，最末一项即为 $t$ 的前缀与 $s$ 的后缀的最长重合，合并可在线性时间内完成，排列枚举不必改动。

我们可以使用 KMP 算法来优化字符串的合并过程。

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

func minimumString(a string, b string, c string) string {
	f := func(s, t string) string {
		if strings.Contains(s, t) {
			return s
		}
		if strings.Contains(t, s) {
			return t
		}
		p := t + "#" + s + "$"
		n := len(p)
		next := make([]int, n)
		next[0] = -1
		for i, j := 2, 0; i < n; {
			if p[i-1] == p[j] {
				j++
				next[i] = j
				i++
			} else if j > 0 {
				j = next[j]
			} else {
				next[i] = 0
				i++
			}
		}
		return s + t[next[n-1]:]
	}
	s := [3]string{a, b, c}
	ans := ""
	for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
		i, j, k := p[0], p[1], p[2]
		t := f(f(s[i], s[j]), s[k])
		if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
			ans = t
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2813. 子序列最大优雅度

困难1 种解法

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

题目、示例与约束

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意：数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

 

示例 1：

输入：items = [[3,2],[5,1],[10,1]], k = 2
输出：17
解释：
在这个例子中，我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。
因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。 

示例 2：

输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出：19
解释：
在这个例子中，我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ，子序列包含 3 种不同类别 [1, 2, 3] 。 
因此，优雅度为 10 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。

示例 3：

输入：items = [[1,1],[2,1],[3,1]], k = 3
输出：7
解释：
在这个例子中，我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6，子序列包含 1 种不同类别 [1] 。
因此，最大优雅度为 6 + 12 = 7 。

 

提示：

• 1 <= items.length == n <= 105
• items[i].length == 2
• items[i][0] == profiti
• items[i][1] == categoryi
• 1 <= profiti <= 109
• 1 <= categoryi <= n
• 1 <= k <= n

方法一：贪心 · Go 实现

思考

优雅度为利润和加上不同类别数的平方，直接枚举长度为 $k$ 的子序列不可行。利润大的项目应优先入选：先取利润前 $k$，用集合记录类别、用栈记下其中重复类别的利润。其后若出现新类别，便弹出栈顶重复项以换入该项目，从而用类别数的平方增量补偿利润损失。

我们可以将所有项目按照利润从大到小排序，先选取前 $k$ 个项目，计算其总利润 $tot$，用一个哈希表 $vis$ 记录这 $k$ 个项目的类别，用一个栈 $dup$ 按顺序记录这 $k$ 个项目中重复类别的利润，用一个变量 $ans$ 记录当前的最大优雅度。

接下来，我们考虑从第 $k+1$ 个项目开始，如果其类别已经在 $vis$ 中，这意味着如果选择该类别，不会使得不同的类别数量增加，因此我们可以直接跳过该项目。如果此前不存在重复类别，我们也可以直接跳过该项目。否则，我们可以考虑将 $dup$ 栈顶的项目（即重复类别中利润最小的项目）替换为当前项目，这样可以使得总利润增加 $p-dup.pop()$，同时不同类别数量增加 $1$，因此我们可以更新 $tot$ 和 $ans$。

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

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

func findMaximumElegance(items [][]int, k int) int64 {
	sort.Slice(items, func(i, j int) bool { return items[i][0] > items[j][0] })
	tot := 0
	vis := map[int]bool{}
	dup := []int{}
	for _, item := range items[:k] {
		p, c := item[0], item[1]
		tot += p
		if vis[c] {
			dup = append(dup, p)
		} else {
			vis[c] = true
		}
	}
	ans := tot + len(vis)*len(vis)
	for _, item := range items[k:] {
		p, c := item[0], item[1]
		if vis[c] || len(dup) == 0 {
			continue
		}
		vis[c] = true
		tot += p - dup[len(dup)-1]
		dup = dup[:len(dup)-1]
		ans = max(ans, tot+len(vis)*len(vis))
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2818. 操作使得分最大

困难1 种解法

标签：栈、贪心、数组、数学、数论、排序、单调栈

题目、示例与约束

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。

一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：

• 选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。
• 从 nums[l, ..., r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
• 将你的分数乘以 x 。

nums[l, ..., r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。

一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5 。

请你返回进行至多 k 次操作后，可以得到的 最大分数 。

由于答案可能很大，请你将结果对 109 + 7 取余后返回。

 

示例 1：

输入：nums = [8,3,9,3,8], k = 2
输出：81
解释：进行以下操作可以得到分数 81 ：
- 选择子数组 nums[2, ..., 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。
81 是可以得到的最高得分。

示例 2：

输入：nums = [19,12,14,6,10,18], k = 3
输出：4788
解释：进行以下操作可以得到分数 4788 ：
- 选择子数组 nums[0, ..., 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。
- 选择子数组 nums[5, ..., 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为  342 * 14 = 4788 。
4788 是可以得到的最高的分。

 

提示：

• 1 <= nums.length == n <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= min(n * (n + 1) / 2, 109)

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

思考

子数组的质数分数由其质因数个数最多的元素决定（并列时取最左）。对每个位置用单调栈求出它作为最高分的左右范围，可贡献 $(i-l)\times (r-i)$ 次操作。次数受 $k$ 限制，故再按数值从大到小贪心取幂，直至用尽 $k$ 次。

我们不妨考虑枚举每个元素 $nums[i]$ 作为质数分数最高的元素，那么我们需要找出左边第一个质数分数大于等于当前元素的位置 $l$，以及右边第一个质数分数大于当前元素的位置 $r$，那么以当前元素为最高质数分数的子数组有 $cnt=(i-l)\times (r-i)$ 个，它对答案的贡献为 $nums[i{]}^{cnt}$。

而题目限制了最多进行 $k$ 次操作，我们可以贪心地从大到小枚举 $nums[i]$，每一次算出其子数组的个数 $cnt$，如果 $cnt\le k$，那么 $nums[i]$ 对答案的贡献就是 $nums[i{]}^{cnt}$，然后我们更新 $k=k-cnt$，继续枚举下一个元素。如果 $cnt>k$，那么 $nums[i]$ 对答案的贡献就是 $nums[i{]}^k$，然后退出循环。

枚举结束，返回答案即可。注意，由于幂次较大，我们需要用到快速幂。

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

func maximumScore(nums []int, k int) int {
	n := len(nums)
	const mod = 1e9 + 7
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	arr := make([][3]int, n)
	left := make([]int, n)
	right := make([]int, n)
	for i, x := range nums {
		left[i] = -1
		right[i] = n
		arr[i] = [3]int{i, primeFactors(x), x}
	}
	stk := []int{}
	for _, e := range arr {
		i, f := e[0], e[1]
		for len(stk) > 0 && arr[stk[len(stk)-1]][1] < f {
			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-- {
		f := arr[i][1]
		for len(stk) > 0 && arr[stk[len(stk)-1]][1] <= f {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i][2] > arr[j][2] })
	ans := 1
	for _, e := range arr {
		i, x := e[0], e[2]
		l, r := left[i], right[i]
		cnt := (i - l) * (r - i)
		if cnt <= k {
			ans = ans * qpow(x, cnt) % mod
			k -= cnt
		} else {
			ans = ans * qpow(x, k) % mod
			break
		}
	}
	return ans
}

func primeFactors(n int) int {
	i := 2
	ans := map[int]bool{}
	for i <= n/i {
		for n%i == 0 {
			ans[i] = true
			n /= i
		}
		i++
	}
	if n > 1 {
		ans[n] = true
	}
	return len(ans)
}

力扣原题 · Doocs 题解来源

2829. k-avoiding 数组的最小总和

中等1 种解法

标签：贪心、数学

题目、示例与约束

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

 

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。 

 

提示：

• 1 <= n, k <= 50

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

思考

数组由 $n$ 个不同正整数构成，且不能同时包含和为 $k$ 的一对，要求和最小。从 $1$ 起贪心选取尚未被禁止的数，并立刻将搭档 $k-i$ 标为不可用，从而始终取当前最小可行值。

我们从正整数 $i=1$ 开始，依次判断 $i$ 是否可以加入数组中，如果可以加入，则将 $i$ 加入数组中，累加到答案中，然后将 $k-i$ 置为已访问，表示 $k-i$ 不能加入数组中。循环直到数组长度为 $n$。

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

func minimumSum(n int, k int) int {
	s, i := 0, 1
	vis := make([]bool, n+k+1)
	for ; n > 0; n-- {
		for vis[i] {
			i++
		}
		if k >= i {
			vis[k-i] = true
		}
		s += i
		i++
	}
	return s
}

力扣原题 · Doocs 题解来源

2834. 找出美丽数组的最小和

中等1 种解法

标签：贪心、数学

题目、示例与约束

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

• nums.length == n.
• nums 由两两互不相同的正整数组成。
• 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 109 + 7。

 

示例 1：

输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。

示例 2：

输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。 
- nums 的长度为 n = 3 。 
- nums 由两两互不相同的正整数组成。 
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。

示例 3：

输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。

 

提示：

• 1 <= n <= 109
• 1 <= target <= 109

方法一：贪心 + 数学 · Go 实现

思考

美丽数组不能同时包含和为 $target$ 的一对，且要求和最小。从 $1$ 起贪心选取时，不超过 $\lfloor target/2\rfloor$ 的数均可取；若还不够 $n$ 个，则从 $target$ 起接着取连续整数。两段均为等差数列，可用通项公式在常数时间内求和。

我们可以贪心地从 $x=1$ 开始构造数组 $nums$，每次选择 $x$，并且排除 $target-x$。

我们不妨记 $m=\lfloor \frac{target}{2}\rfloor$。

如果 $x<=m$，那么我们可以选择的数有 $1,2,\cdots ,n$，所以数组的和为 $\lfloor \frac{(1+n)n}{2}\rfloor$。

如果 $x>m$，那么我们可以选择的数有 $1,2,\cdots ,m$，共 $m$ 个数，以及 $n-m$ 个从 $target$ 开始的数，所以数组的和为 $\lfloor \frac{(1+m)m}{2}\rfloor +\lfloor \frac{(target+target+n-m-1)(n-m)}{2}\rfloor$。

注意，我们需要对结果取模 ${10}^9+7$。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

func minimumPossibleSum(n int, target int) int {
	const mod int = 1e9 + 7
	m := target / 2
	if n <= m {
		return (n + 1) * n / 2 % mod
	}
	a := (m + 1) * m / 2 % mod
	b := (target + target + n - m - 1) * (n - m) / 2 % mod
	return (a + b) % mod
}

力扣原题 · Doocs 题解来源

2835. 使子序列的和等于目标的最少操作次数

困难1 种解法

标签：贪心、位运算、数组

题目、示例与约束

给你一个下标从 0 开始的数组 nums ，它包含 非负 整数，且全部为 2 的幂，同时给你一个整数 target 。

一次操作中，你必须对数组做以下修改：

• 选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
• 将 nums[i] 从数组中删除。
• 在 nums 的 末尾 添加 两个 数，值都为 nums[i] / 2 。

你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。

数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。

 

示例 1：

输入：nums = [1,2,8], target = 7
输出：1
解释：第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。
这时候，nums 包含子序列 [1,2,4] ，和为 7 。
无法通过更少的操作得到和为 7 的子序列。

示例 2：

输入：nums = [1,32,1,2], target = 12
输出：2
解释：第一次操作中，我们选择元素 nums[1] 。数组变为 nums = [1,1,2,16,16] 。
第二次操作中，我们选择元素 nums[3] 。数组变为 nums = [1,1,2,16,8,8] 。
这时候，nums 包含子序列 [1,1,2,8] ，和为 12 。
无法通过更少的操作得到和为 12 的子序列。

示例 3：

输入：nums = [1,32,1], target = 35
输出：-1
解释：无法得到和为 35 的子序列。

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 230
• nums 只包含非负整数，且均为 2 的幂。
• 1 <= target < 231

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

思考

操作把一个大于 $1$ 的幂次拆成两个相等的较小幂次，数组总和不变。若总和小于 $target$ 则无解。按位统计后，从低到高凑齐 $target$ 的每一个 $1$：不足时把更高位拆下来，拆一次计一次操作。

观察题目中的操作，我们发现，每次操作实际上是把一个大于 $1$ 的数拆分为两个相等的数，这意味着操作后数组的元素和不会发生变化。因此，如果数组的元素和 $s$ 小于 $target$，则无法通过题目描述的操作得到和为 $target$ 的子序列，直接返回 $-1$ 即可。否则，我们一定可以通过拆分操作，使得数组某个子序列的元素和等于 $target$。

另外，拆分操作实际上会把二进制高位为 $1$ 的数置为 $0$，并把低一位的数加上 $2$。因此，我们先用一个长度为 $32$ 的数组记录数组 $nums$ 所有元素的二进制表示中每个二进制位上 $1$ 的出现次数。

接下来，从 $target$ 的低位开始遍历，对于 $target$ 的第 $i$ 位，如果当前位数字为 $0$，则直接跳过，即 $i=i+1$。如果当前位数字为 $1$，我们需要在数组 $cnt$ 中，找到最小的数字 $j$（其中 $j\ge i$），使得 $cnt[j]>0$，然后我们将该位的数字 $1$ 往低位 $i$ 拆分，即把 $cnt[j]$ 减 $1$，而 $cnt[i..j-1]$ 的每一位置为 $1$，操作次数为 $j-i$。接下来，我们令 $j=i$，然后 $i=i+1$。重复上述操作，直到 $i$ 超出数组 $cnt$ 的下标范围，返回此时的操作次数。

注意，如果 $j<i$，实际上两个低位的 $1$ 可以合并成一个高一位的 $1$。因此，如果 $j<i$，我们将 $\frac{cnt[j]}{2}$ 加到 $cnt[j+1]$ 中，并将 $cnt[j]$ 取模 $2$，然后令 $j=j+1$，继续上述操作。

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

func minOperations(nums []int, target int) (ans int) {
	s := 0
	cnt := [32]int{}
	for _, x := range nums {
		s += x
		for i := 0; i < 32; i++ {
			if x>>i&1 > 0 {
				cnt[i]++
			}
		}
	}
	if s < target {
		return -1
	}
	var i, j int
	for {
		for i < 32 && target>>i&1 == 0 {
			i++
		}
		if i == 32 {
			return
		}
		for j < i {
			cnt[j+1] += cnt[j] >> 1
			cnt[j] %= 2
			j++
		}
		for cnt[j] == 0 {
			cnt[j] = 1
			j++
		}
		ans += j - i
		cnt[j]--
		j = i
		i++
	}
}

力扣原题 · Doocs 题解来源

2842. 统计一个字符串的 k 子序列美丽值最大的数目

困难1 种解法

标签：贪心、哈希表、数学、字符串、组合数学、排序、费马小定理

题目、示例与约束

给你一个字符串 s 和一个整数 k 。

k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。

定义 f(c) 为字符 c 在 s 中出现的次数。

k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。

比方说，s = "abbbdd" 和 k = 2 ，我们有：

• f('a') = 1, f('b') = 3, f('d') = 2
• s 的部分 k 子序列为：
  • "abbbdd" -> "ab" ，美丽值为 f('a') + f('b') = 4
  • "abbbdd" -> "ad" ，美丽值为 f('a') + f('d') = 3
  • "abbbdd" -> "bd" ，美丽值为 f('b') + f('d') = 5

请你返回一个整数，表示所有 k 子序列 里面 美丽值 是 最大值 的子序列数目。由于答案可能很大，将结果对 109 + 7 取余后返回。

一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。

注意：

• f(c) 指的是字符 c 在字符串 s 的出现次数，不是在 k 子序列里的出现次数。
• 两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。

 

示例 1：

输入：s = "bcca", k = 2
输出：4
解释：s 中我们有 f('a') = 1 ，f('b') = 1 和 f('c') = 2 。
s 的 k 子序列为：
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('a') = 2
bcca ，美丽值为 f('c') + f('a') = 3
bcca ，美丽值为 f('c') + f('a') = 3
总共有 4 个 k 子序列美丽值为最大值 3 。
所以答案为 4 。

示例 2：

输入：s = "abbcd", k = 4
输出：2
解释：s 中我们有 f('a') = 1 ，f('b') = 2 ，f('c') = 1 和 f('d') = 1 。
s 的 k 子序列为：
abbcd ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5
abbcd ，美丽值为 f('a') + f('b') + f('c') + f('d') = 5 
总共有 2 个 k 子序列美丽值为最大值 5 。
所以答案为 2 。

 

提示：

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

方法一：贪心 + 组合数学 · Go 实现

思考

美丽值是子序列中各字符频次之和，且字符须互异。应优先选用频次最高的若干字符。将频次降序排列，严格大于第 $k$ 大频次的字符必须全选；并列在阈值上的字符用组合数从中选满剩余名额，再乘以该频次的幂。

我们先用哈希表 $f$ 统计字符串 $s$ 中每个字符的出现次数，即 $f[c]$ 表示字符 $c$ 在字符串 $s$ 中出现的次数。

由于 $k$ 子序列是字符串 $s$ 中一个长度为 $k$ 的子序列，且字符唯一，因此，如果 $f$ 中不同字符的个数小于 $k$，那么不存在 $k$ 子序列，直接返回 $0$ 即可。

否则，要使得 $k$ 子序列的美丽值最大，我们需要尽可能地让美丽值大的字符尽可能地多地出现在 $k$ 子序列中。因此，我们可以对 $f$ 中的值进行倒序排序，得到一个数组 $vs$。

我们记数组 $vs$ 第 $k$ 个字符的出现次数为 $val$，一共有 $x$ 个字符出现的次数为 $val$。

那么我们先找出出现次数大于 $val$ 的字符，将每个字符出现的次数相乘，得到初始答案 $ans$，剩余的需要选取的字符个数更新为 $k$。我们需要从 $x$ 个字符中选取 $k$ 个字符，因此答案需要乘上组合数 $C_x^k$，最后再乘上 $va{l}^k$，即 $ans=ans\times C_x^k\times va{l}^k$。

注意，这里需要用到快速幂，以及取模操作。

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

func countKSubsequencesWithMaxBeauty(s string, k int) int {
	f := [26]int{}
	cnt := 0
	for _, c := range s {
		f[c-'a']++
		if f[c-'a'] == 1 {
			cnt++
		}
	}
	if cnt < k {
		return 0
	}
	vs := []int{}
	for _, x := range f {
		if x > 0 {
			vs = append(vs, x)
		}
	}
	sort.Slice(vs, func(i, j int) bool {
		return vs[i] > vs[j]
	})
	const mod int = 1e9 + 7
	ans := 1
	val := vs[k-1]
	x := 0
	for _, v := range vs {
		if v == val {
			x++
		}
	}
	for _, v := range vs {
		if v == val {
			break
		}
		k--
		ans = ans * v % mod
	}
	c := make([][]int, x+1)
	for i := range c {
		c[i] = make([]int, x+1)
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod
		}
	}
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	ans = (ans * c[x][k] % mod) * qpow(val, k) % mod
	return ans
}

力扣原题 · Doocs 题解来源

2844. 生成特殊数字的最少操作

中等1 种解法

标签：贪心、数学、字符串、枚举

题目、示例与约束

给你一个下标从 0 开始的字符串 num ，表示一个非负整数。

在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。

返回最少需要多少次操作可以使 num 变成特殊数字。

如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。

 

 

示例 1：

输入：num = "2245047"
输出：2
解释：删除数字 num[5] 和 num[6] ，得到数字 "22450" ，可以被 25 整除。
可以证明要使数字变成特殊数字，最少需要删除 2 位数字。

示例 2：

输入：num = "2908305"
输出：3
解释：删除 num[3]、num[4] 和 num[6] ，得到数字 "2900" ，可以被 25 整除。
可以证明要使数字变成特殊数字，最少需要删除 3 位数字。

示例 3：

输入：num = "10"
输出：1
解释：删除 num[0] ，得到数字 "0" ，可以被 25 整除。
可以证明要使数字变成特殊数字，最少需要删除 1 位数字。

 

提示

• 1 <= num.length <= 100
• num 仅由数字 '0' 到 '9' 组成
• num 不含任何前导零

方法一：记忆化搜索 · Go 实现

思考

能被 $25$ 整除即模 $25$ 为 $0$，允许删除任意位。从左到右决定保留或删除当前位， $dfs(i,k)$ 表示处理到第 $i$ 位、当前余数为 $k$ 时的最少删除次数；删则余数不变，留则余数变为 $(k\cdot 10+d)mod25$。

我们注意到，整数 $x$ 要能被 $25$ 整除，即 $xmod25=0$。因此，我们可以设计一个函数 $dfs(i,k)$，表示从字符串 $num$ 的第 $i$ 位开始，且当前数字模 $25$ 的结果为 $k$ 的情况下，要使得数字变成特殊数字，最少需要删除多少位数字。那么答案为 $dfs(0,0)$。

函数 $dfs(i,k)$ 的执行逻辑如下：

• 如果 $i=n$，即已经处理完字符串 $num$ 的所有位，那么如果 $k=0$，则当前数字可以被 $25$ 整除，返回 $0$，否则返回 $n$；
• 否则，第 $i$ 位可以被删除，此时需要删除一位，即 $dfs(i+1,k)+1$；第 $i$ 位不删除，那么 $k$ 的值变为 $(k\times 10+\mathit{\text{num}}[i])mod25$，即 $dfs(i+1,(k\times 10+\mathit{\text{num}}[i])mod25)$。取这两者的最小值即可。

为了防止重复计算，我们可以使用记忆化的方法优化时间复杂度。

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

func minimumOperations(num string) int {
	n := len(num)
	f := make([][25]int, n)
	for i := range f {
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, k int) int
	dfs = func(i, k int) int {
		if i == n {
			if k == 0 {
				return 0
			}
			return n
		}
		if f[i][k] != -1 {
			return f[i][k]
		}
		f[i][k] = dfs(i+1, k) + 1
		f[i][k] = min(f[i][k], dfs(i+1, (k*10+int(num[i]-'0'))%25))
		return f[i][k]
	}
	return dfs(0, 0)
}

力扣原题 · Doocs 题解来源

2847. 给定数字乘积的最小数字 🔒

中等1 种解法

标签：贪心、数学

题目、示例与约束

给定一个 正 整数 n。

返回一个字符串，表示使其各位数字的乘积等于 n 的 最小正整数，如果不存在这样的数字，则返回 "-1" 。

 

示例 1：

输入：n = 105
输出："357"
解释：3 * 5 * 7 = 105。可以证明，357 是各位数字的乘积等于 105 的最小数字。因此答案为 "357"。

示例 2：

输入：n = 7
输出："7"
解释：由于 7 只有一位数字，其各位数字的乘积为 7。由于数字 1 到 6 的乘积分别为 1 到 6，所以答案为 "7"。可以证明 7 是乘积等于 7 的最小数字。

示例 3：

输入：n = 44
输出："-1"
解释：可以证明，没有数字的各位数字乘积等于 44。因此答案为 "-1"。

 

提示：

• 1 <= n <= 1015

方法一：质因数分解 + 贪心 · Go 实现

思考

所求数的各位之积为 $n$，且字典序最小。若 $n$ 含大于 $9$ 的质因子则无解。从 $9$ 到 $2$ 尽量拆出较大数位，再从小到大拼接，以保证位数最少且字典序最小； $n=1$ 时答案为 $1$。

我们考虑对数字 $n$ 进行质因数分解，如果 $n$ 的质因数中存在大于 $9$ 的质数，那么一定无法找到符合条件的数字，因为大于 $9$ 的质数无法通过 $1$ 到 $9$ 的数字相乘得到，例如 $11$ 无法通过 $1$ 到 $9$ 的数字相乘得到，因此我们只需要考虑 $n$ 的质因数中是否存在大于 $9$ 的质数即可，如果存在，直接返回 $-1$。

否则，如果质因数中包含 $7$ 和 $5$，那么数字 $n$ 首先可以拆分为若干个 $7$ 和 $5$，两个数字 $3$ 可以合成一个数字 $9$，三个数字 $2$ 可以合成一个数字 $8$，数字 $2$ 和数字 $3$ 可以合成一个数字 $6$，因此我们只需要将数字拆分为 $[2,..9]$ 的数字即可，我们可以使用贪心的方法，优先拆分出数字 $9$，然后拆分出数字 $8$，依次类推。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

func smallestNumber(n int64) string {
	cnt := [10]int{}
	for i := 9; i > 1; i-- {
		for n%int64(i) == 0 {
			cnt[i]++
			n /= int64(i)
		}
	}
	if n != 1 {
		return "-1"
	}
	sb := &strings.Builder{}
	for i := 2; i < 10; i++ {
		for j := 0; j < cnt[i]; j++ {
			sb.WriteByte(byte(i) + '0')
		}
	}
	ans := sb.String()
	if len(ans) > 0 {
		return ans
	}
	return "1"
}

力扣原题 · Doocs 题解来源

2856. 删除数对后的最小数组长度

中等1 种解法

标签：贪心、数组、哈希表、双指针、二分查找、计数

题目、示例与约束

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

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

• 选择 两个 下标 i 和 j ，满足 nums[i] < nums[j] 。
• 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

 

示例 1：

输入：nums = [1,2,3,4]

输出：0

解释：

示例 2：

输入：nums = [1,1,2,2,3,3]

输出：0

解释：

示例 3：

输入：nums = [1000000000,1000000000]

输出：2

解释：

由于两个数字相等，不能删除它们。

示例 4：

输入：nums = [2,3,4,4,4]

输出：1

解释：

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• nums 是 非递减 数组。

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

思考

每次删除两个不同的数。剩余长度由出现次数最多的值决定：若某值次数超过半数，删完其它数后它仍会剩下。用大根堆反复取出两个最大频次各减一，模拟配对过程，也可得到同一结果。

我们用一个哈希表 $cnt$ 统计数组 $nums$ 中每个元素的出现次数，然后将 $cnt$ 中的每个值加入一个优先队列（大根堆） $pq$ 中。每次从 $pq$ 中取出两个元素 $x$ 和 $y$，将它们的值减一，如果减一后的值仍大于 $0$，则将减一后的值重新加入 $pq$。每次从 $pq$ 中取出两个元素，表示将数组中的两个数对删除，因此数组的长度减少 $2$。当 $pq$ 的大小小于 $2$ 时，停止删除操作。

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

func minLengthAfterRemovals(nums []int) int {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	h := &hp{}
	for _, x := range cnt {
		h.push(x)
	}
	ans := len(nums)
	for h.Len() > 1 {
		x, y := h.pop(), h.pop()
		if x > 1 {
			h.push(x - 1)
		}
		if y > 1 {
			h.push(y - 1)
		}
		ans -= 2
	}
	return 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
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }

力扣原题 · Doocs 题解来源