LeetCode Go · 贪心（7）

来源与许可

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

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

2132. 用邮票贴满网格图

困难1 种解法

标签：贪心、数组、矩阵、前缀和

题目、示例与约束

给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。

给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下限制和要求：

覆盖所有空格子。
不覆盖任何 被占据 的格子。
我们可以放入任意数目的邮票。
邮票可以相互有重叠部分。
邮票不允许旋转。
邮票必须完全在矩阵内。

如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。

示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
输出：false 
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：

m == grid.length
n == grid[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 2 * 10⁵
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 10⁵

方法一：二维前缀和 + 二维差分 · Go 实现

思考

每张邮票必须完全落在空格子上，且每个空格至少被盖一次。若枚举每个合法左上角再把矩形逐格标记，最坏 $O (m n \cdot h w)$ ，在网格与邮票都较大时不可行。

二维前缀和可 $O (1)$ 判断一块 $h \times w$ 是否全空；所有成功盖印再用二维差分记录覆盖次数，最后还原差分，检查每个空格的覆盖是否为正。

先建占据前缀 $s$ ，对每个可放位置在差分 $d$ 上 $+ 1$ ，再还原 $d$ 并拒绝仍为 $0$ 的空格。

根据题目描述，每一个空格子都必须被邮票覆盖，而且不能覆盖任何被占据的格子。因此，我们可以遍历二维矩阵，对于每个格子，如果以该格子为左上角的 $s t a m p H e i g h t \times s t a m p W i d t h$ 的区域内的所有格子都是空格子（即没有被占据），那么我们就可以在该格子处放置一个邮票。

为了快速判断一个区域内的所有格子是否都是空格子，我们可以使用二维前缀和。我们用 $s_{i, j}$ 表示二维矩阵中从 $(1, 1)$ 到 $(i, j)$ 的子矩阵中被占据的格子的数量。即 $s_{i, j} = s_{i - 1, j} + s_{i, j - 1} - s_{i - 1, j - 1} + g r i d_{i - 1, j - 1}$ 。

那么以 $(i, j)$ 为左上角，且高度和宽度分别为 $s t a m p H e i g h t$ 和 $s t a m p W i d t h$ 的子矩阵的右下角坐标为 $(x, y) = (i + s t a m p H e i g h t - 1, j + s t a m p W i d t h - 1)$ ，我们可以通过 $s_{x, y} - s_{x, j - 1} - s_{i - 1, y} + s_{i - 1, j - 1}$ 来计算出该子矩阵中被占据的格子的数量。如果该子矩阵中被占据的格子的数量为 $0$ ，那么我们就可以在 $(i, j)$ 处放置一个邮票，放置邮票后，这 $s t a m p H e i g h t \times s t a m p W i d t h$ 的区域内的所有格子都会变成被占据的格子，我们可以用二维差分数组 $d$ 来记录这一变化。即：

\begin{aligned} d_{i, j} & \leftarrow d_{i, j} + 1 \\ d_{i, y + 1} & \leftarrow d_{i, y + 1} - 1 \\ d_{x + 1, j} & \leftarrow d_{x + 1, j} - 1 \\ d_{x + 1, y + 1} & \leftarrow d_{x + 1, y + 1} + 1 \end{aligned}

最后，我们对二维差分数组 $d$ 进行前缀和运算，可以得出每个格子被邮票覆盖的次数。如果某个格子没有被占据，且被邮票覆盖的次数为 $0$ ，那么我们就无法将邮票放置在该格子处，因此我们需要返回 $false$ 。如果所有“没被占据的格子”都成功被邮票覆盖，返回 $true$ 。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是二维矩阵的高度和宽度。

func possibleToStamp(grid [][]int, stampHeight int, stampWidth int) bool {
	m, n := len(grid), len(grid[0])
	s := make([][]int, m+1)
	for i := range s {
		s[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grid[i-1][j-1]
		}
	}

	d := make([][]int, m+2)
	for i := range d {
		d[i] = make([]int, n+2)
	}

	for i := 1; i+stampHeight-1 <= m; i++ {
		for j := 1; j+stampWidth-1 <= n; j++ {
			x, y := i+stampHeight-1, j+stampWidth-1
			if s[x][y]-s[x][j-1]-s[i-1][y]+s[i-1][j-1] == 0 {
				d[i][j]++
				d[i][y+1]--
				d[x+1][j]--
				d[x+1][y+1]++
			}
		}
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]
			if grid[i-1][j-1] == 0 && d[i][j] == 0 {
				return false
			}
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2136. 全部开花的最早一天

困难1 种解法

标签：贪心、数组、排序

题目、示例与约束

你有 n 枚花的种子。每枚种子必须先种下，才能开始生长、开花。播种需要时间，种子的生长也是如此。给你两个下标从 0 开始的整数数组 plantTime 和 growTime ，每个数组的长度都是 n ：

plantTime[i] 是播种第 i 枚种子所需的 完整天数 。每天，你只能为播种某一枚种子而劳作。无须连续几天都在种同一枚种子，但是种子播种必须在你工作的天数达到 plantTime[i] 之后才算完成。
growTime[i] 是第 i 枚种子完全种下后生长所需的 完整天数 。在它生长的最后一天之后，将会开花并且永远绽放。

从第 0 开始，你可以按任意顺序播种种子。

返回所有种子都开花的最早一天是第几天。

示例 1：

输入：plantTime = [1,4,3], growTime = [2,3,1]
输出：9
解释：灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。
一种最优方案是：
第 0 天，播种第 0 枚种子，种子生长 2 整天。并在第 3 天开花。
第 1、2、3、4 天，播种第 1 枚种子。种子生长 3 整天，并在第 8 天开花。
第 5、6、7 天，播种第 2 枚种子。种子生长 1 整天，并在第 9 天开花。
因此，在第 9 天，所有种子都开花。

示例 2：

输入：plantTime = [1,2,3,2], growTime = [2,1,2,1]
输出：9
解释：灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。 
一种最优方案是：
第 1 天，播种第 0 枚种子，种子生长 2 整天。并在第 4 天开花。
第 0、3 天，播种第 1 枚种子。种子生长 1 整天，并在第 5 天开花。
第 2、4、5 天，播种第 2 枚种子。种子生长 2 整天，并在第 8 天开花。
第 6、7 天，播种第 3 枚种子。种子生长 1 整天，并在第 9 天开花。
因此，在第 9 天，所有种子都开花。

示例 3：

输入：plantTime = [1], growTime = [1]
输出：2
解释：第 0 天，播种第 0 枚种子。种子需要生长 1 整天，然后在第 2 天开花。
因此，在第 2 天，所有种子都开花。

提示：

n == plantTime.length == growTime.length
1 <= n <= 10⁵
1 <= plantTime[i], growTime[i] <= 10⁴

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

思考

每天只能播种一枚种子，播种时间之和与顺序无关，开花日取决于「该种子播完时刻加上生长时间」的最大值。若先种生长短的，长生长者会更晚结束。

应尽早开始生长时间长的种子，按其 $growTime$ 降序播种。前缀播种天数 $t$ 累加 $plantTime$ ，该种子开花日为 $t + growTime$ ，全程取最大。

按生长时间排序后一次扫描即可。

根据题目描述，我们知道，每一天只能为一枚种子进行播种，因此不管什么播种顺序，所有种子的播种时间之和总是等于 $\sum_{i = 0}^{n - 1} p l a n t T i m e [i]$ 。那么，为了让尽快让所有种子开花，我们应该尽快播种生长时间最长的种子。因此，我们可以对所有种子按照生长时间从大到小进行排序，然后依次进行播种。

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

func earliestFullBloom(plantTime []int, growTime []int) (ans int) {
	n := len(plantTime)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return growTime[idx[j]] < growTime[idx[i]] })
	t := 0
	for _, i := range idx {
		t += plantTime[i]
		ans = max(ans, t+growTime[i])
	}
	return
}

力扣原题 · Doocs 题解来源

2139. 得到目标值的最少行动次数

中等2 种解法

标签：贪心、数学

题目、示例与约束

你正在玩一个整数游戏。从整数 1 开始，期望得到整数 target 。

在一次行动中，你可以做下述两种操作之一：

递增，将当前整数的值加 1（即， x = x + 1）。
加倍，使当前整数的值翻倍（即，x = 2 * x）。

在整个游戏过程中，你可以使用递增操作任意次数。但是只能使用加倍操作至多 maxDoubles 次。

给你两个整数 target 和 maxDoubles ，返回从 1 开始得到 target 需要的最少行动次数。

示例 1：

输入：target = 5, maxDoubles = 0
输出：4
解释：一直递增 1 直到得到 target 。

示例 2：

输入：target = 19, maxDoubles = 2
输出：7
解释：最初，x = 1 。
递增 3 次，x = 4 。
加倍 1 次，x = 8 。
递增 1 次，x = 9 。
加倍 1 次，x = 18 。
递增 1 次，x = 19 。

示例 3：

输入：target = 10, maxDoubles = 4
输出：4
解释：
最初，x = 1 。 
递增 1 次，x = 2 。 
加倍 1 次，x = 4 。 
递增 1 次，x = 5 。 
加倍 1 次，x = 10 。

提示：

1 <= target <= 10⁹
0 <= maxDoubles <= 100

方法一：倒推 + 贪心 · Go 实现

思考

从 $1$ 加到 $target$ ，加倍次数至多为 $maxDoubles$ 。正向搜索加与乘的交错顺序分支很多。倒着看：偶数且仍有加倍次数时应优先折半，否则只能减一，因为加倍对应倒推时的除二，应尽量用在较大的偶数上。

$target$ 很大而加倍次数很少，倒推步数约为 $O (min (\log target, maxDoubles))$ 。无加倍次数时答案就是 $target - 1$ 。

递归处理：偶数且 $maxDoubles > 0$ 则除二并消耗一次加倍，否则减一。

我们不妨从最终的状态开始倒推，假设最终的状态为 $t a r g e t$ ，那么我们可以得到 $t a r g e t$ 的前一个状态为 $t a r g e t - 1$ 或者 $t a r g e t / 2$ ，这取决于 $t a r g e t$ 的奇偶性以及 $m a x D o u b l e s$ 的值。

如果 $t a r g e t = 1$ ，那么不需要任何操作，直接返回 $0$ 即可。

如果 $m a x D o u b l e s = 0$ ，那么我们只能使用递增操作，因此我们需要 $t a r g e t - 1$ 次操作。

如果 $t a r g e t$ 是偶数且 $m a x D o u b l e s > 0$ ，那么我们可以使用加倍操作，因此我们需要 $1$ 次操作，然后递归求解 $t a r g e t / 2$ 和 $m a x D o u b l e s - 1$ 。

如果 $t a r g e t$ 是奇数，那么我们只能使用递增操作，因此我们需要 $1$ 次操作，然后递归求解 $t a r g e t - 1$ 和 $m a x D o u b l e s$ 。

时间复杂度 $O (min (\log t a r g e t, m a x D o u b l e s))$ ，空间复杂度 $O (min (\log t a r g e t, m a x D o u b l e s))$ 。

我们也可以将上述过程改为迭代的方式，这样可以避免递归的空间开销。

func minMoves(target int, maxDoubles int) int {
	if target == 1 {
		return 0
	}
	if maxDoubles == 0 {
		return target - 1
	}
	if target%2 == 0 && maxDoubles > 0 {
		return 1 + minMoves(target>>1, maxDoubles-1)
	}
	return 1 + minMoves(target-1, maxDoubles)
}

方法二 · Go 实现

思考

方法一的递归深度与倒推步数相同，可改成迭代以去掉栈空间。

当仍有加倍次数且 $target > 1$ 时，奇数先减一，偶数则右移并消耗加倍；加倍用尽后把剩余的 $target - 1$ 一次加上。

逻辑与方法一相同，只是写成循环。

func minMoves(target int, maxDoubles int) (ans int) {
	for maxDoubles > 0 && target > 1 {
		ans++
		if target&1 == 1 {
			target--
		} else {
			maxDoubles--
			target >>= 1
		}
	}
	ans += target - 1
	return
}

力扣原题 · Doocs 题解来源

2141. 同时运行 N 台电脑的最长时间

困难1 种解法

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

题目、示例与约束

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑运行 batteries[i] 分钟。你想使用这些电池让全部 n 台电脑同时运行。

一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的最长分钟数。

示例 1：

输入：n = 2, batteries = [3,3,3]
输出：4
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。

示例 2：

输入：n = 2, batteries = [1,1,1,1]
输出：2
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。

提示：

1 <= n <= batteries.length <= 10⁵
1 <= batteries[i] <= 10⁹

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

思考

若能同时运行 $t$ 分钟，则也能运行更短时间，具有单调性。 $t$ 的上界为电量总和，枚举 $t$ 不可行。

一块电池对时长 $t$ 的有效贡献至多为 $t$ （同一时刻只能供一台），因此当且仅当 $\sum_{i} min (b_{i}, t) \geq n \cdot t$ 时可行。在 $[0, \sum b_{i}]$ 上二分 $t$ 。

每次用线性扫描验证中间值，取最大可行 $t$ 。

我们注意到，如果我们可以让 $n$ 台电脑同时运行 $t$ 分钟，那么我们也可以让 $n$ 台电脑同时运行 $t^{'} \leq t$ 分钟，这存在着单调性。因此，我们可以使用二分查找的方法找到最大的 $t$ 。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = \sum_{i = 0}^{n - 1} b a t t e r i e s [i]$ 。每次二分查找的过程中，我们使用一个变量 $m i d$ 表示当前的中间值，即 $m i d = (l + r + 1) >> 1$ 。我们判断是否存在一种方案，使得 $n$ 台电脑同时运行 $m i d$ 分钟。如果存在，那么我们就将 $l$ 更新为 $m i d$ ，否则我们将 $r$ 更新为 $m i d - 1$ 。最后，我们返回 $l$ 即为答案。

问题转化为如何判断是否存在一种方案，使得 $n$ 台电脑同时运行 $m i d$ 分钟。如果一个电池可以运行的分钟数大于 $m i d$ ，由于电脑同时运行 $m i d$ 分钟，而一个电池同一时间只能供电一台电脑，因此我们只能使用这个电池 $m i d$ 分钟。如果一个电池可以运行的分钟数小于等于 $m i d$ ，我们可以使用这个电池的全部电量。因此，我们统计所有电池可以供电的分钟数之和 $s$ ，如果 $s \geq n \times m i d$ ，那么我们就可以使得 $n$ 台电脑同时运行 $m i d$ 分钟。

时间复杂度 $O (n \times \log M)$ ，其中 $M$ 为所有电池的电量之和，空间复杂度 $O (1)$ 。

func maxRunTime(n int, batteries []int) int64 {
	l, r := 0, 0
	for _, x := range batteries {
		r += x
	}
	for l < r {
		mid := (l + r + 1) >> 1
		s := 0
		for _, x := range batteries {
			s += min(x, mid)
		}
		if s >= n*mid {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return int64(l)
}

力扣原题 · Doocs 题解来源

2144. 打折购买糖果的最小开销

简单1 种解法

标签：贪心、数组、排序

题目、示例与约束

一家商店正在打折销售糖果。每购买两个糖果，商店会免费送一个糖果。

免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。

比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。

给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得所有糖果的最小总开销。

示例 1：

输入：cost = [1,2,3]
输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。

示例 2：

输入：cost = [6,5,7,9,2,2]
输出：23
解释：最小总开销购买糖果方案为：
- 购买价格为 9 和 7 的糖果
- 免费获得价格为 6 的糖果
- 购买价格为 5 和 2 的糖果
- 免费获得价格为 2 的最后一个糖果
因此，最小总开销为 9 + 7 + 5 + 2 = 23 。

示例 3：

输入：cost = [5,5]
输出：10
解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。
所以总最小开销为 5 + 5 = 10 。

提示：

1 <= cost.length <= 100
1 <= cost[i] <= 100

方法一：贪心 · Go 实现

思考

每买两颗可免费获得一颗不超过二者较便宜者的糖。为让免费糖尽可能贵，应优先把贵的糖放进付费位置。枚举分组是多余的。

按价格降序排列后，每三颗中的第三颗免费，总开销为全部价格减去这些位置。

排序后用切片 $cost [2 :: 3]$ 求和并从总和中减去。

我们可以先将糖果按照价格从高到低排序，然后每三个糖果中取两个糖果，这样可以保证免费获得的糖果价格最高，从而使得总开销最小。

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

func minimumCost(cost []int) (ans int) {
	sort.Ints(cost)
	for i := len(cost) - 1; i >= 0; i -= 3 {
		ans += cost[i]
		if i > 0 {
			ans += cost[i-1]
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2160. 拆分数位后四位数字的最小和

简单1 种解法

标签：贪心、数学、排序

题目、示例与约束

给你一个四位正整数 num 。请你使用 num 中的数位，将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ，且 num 中所有数位都必须使用。

比方说，给你 num = 2932 ，你拥有的数位包括：两个 2 ，一个 9 和一个 3 。一些可能的 [new1, new2] 数对为 [22, 93]，[23, 92]，[223, 9] 和 [2, 329] 。

请你返回可以得到的 new1 和 new2 的最小和。

示例 1：

输入：num = 2932
输出：52
解释：可行的 [new1, new2] 数对为 [29, 23] ，[223, 9] 等等。
最小和为数对 [29, 23] 的和：29 + 23 = 52 。

示例 2：

输入：num = 4009
输出：13
解释：可行的 [new1, new2] 数对为 [0, 49] ，[490, 0] 等等。
最小和为数对 [4, 9] 的和：4 + 9 = 13 。

提示：

1000 <= num <= 9999

方法一 · Go 实现

思考

四位数字拆成两个整数，要求和最小。前导零允许。枚举所有拆分方式数量很少，但更直接的是让两个数都尽量小，即较小的两个数字做十位。

取出四位排序后，十位取最小的两个，个位取剩下两个。

和为 $10 (a + b) + c + d$ 。

func minimumSum(num int) int {
	var nums []int
	for num > 0 {
		nums = append(nums, num%10)
		num /= 10
	}
	sort.Ints(nums)
	return 10*(nums[0]+nums[1]) + nums[2] + nums[3]
}

力扣原题 · Doocs 题解来源

2170. 使数组变成交替数组的最少操作数

中等1 种解法

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

题目、示例与约束

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

如果满足下述条件，则数组 nums 是一个 交替数组 ：

nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。

在一步操作中，你可以选择下标 i 并将 nums[i] 更改为任一正整数。

返回使数组变成交替数组的 最少操作数 。

示例 1：

输入：nums = [3,1,3,2,4,3]
输出：3
解释：
使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。
在这种情况下，操作数为 3 。
可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。

示例 2：

输入：nums = [1,2,2,2,2]
输出：2
解释：
使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1].
在这种情况下，操作数为 2 。
注意，数组不能转换成 [2,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

方法一：维护奇偶位置的计数 · Go 实现

思考

交替数组要求奇偶下标各自恒等且两值不同。一次操作改一个位置，最少修改等于「该奇偶位上不选目标值的个数」。需为偶数位、奇数位各选一个出现最多的值，且二者不能相同。

分别统计偶、奇下标的最高频与次高频。若二者众数不同，保留它们；若相同，则在「偶位众数 + 奇位次众数」与相反组合中取保留更多的那种。

函数 $f$ 扫一遍计数并维护前两名，答案为 $n$ 减去所选频次之和。

根据题目描述，我们可以知道，如果数组 $nums$ 是一个交替数组，那么数组中的奇数位置和偶数位置的元素一定是不同的，且奇数位置的元素相同，偶数位置的元素也相同。

要使得数组 $nums$ 变成交替数组的操作数最少，我们可以通过统计奇数位置和偶数位置的元素的出现次数，找到偶数位置出现次数最多的两个元素 $a_{0}$ 和 $a_{2}$ ，以及对应的出现次数 $a_{1}$ 和 $a_{3}$ ；再找到奇数位置出现次数最多的两个元素 $b_{0}$ 和 $b_{2}$ ，以及对应的出现次数 $b_{1}$ 和 $b_{3}$ 。

如果 $a_{0} \neq b_{0}$ ，那么我们可以将数组 $nums$ 中偶数位置的元素全部变成 $a_{0}$ ，奇数位置的元素全部变成 $b_{0}$ ，这样操作数为 $n - (a_{1} + b_{1})$ ；如果 $a_{0} = b_{0}$ ，那么我们可以将数组 $nums$ 中偶数位置的元素全部变成 $a_{0}$ ，奇数位置的元素全部变成 $b_{2}$ ，或者将数组 $nums$ 中偶数位置的元素全部变成 $a_{2}$ ，奇数位置的元素全部变成 $b_{0}$ ，这样操作数为 $n - max (a_{1} + b_{3}, a_{3} + b_{1})$ 。

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

func minimumOperations(nums []int) int {
	f := func(i int) [4]int {
		cnt := make(map[int]int)
		for ; i < len(nums); i += 2 {
			cnt[nums[i]]++
		}

		k1, k2 := 0, 0
		for k, v := range cnt {
			if cnt[k1] < v {
				k2, k1 = k1, k
			} else if cnt[k2] < v {
				k2 = k
			}
		}
		return [4]int{k1, cnt[k1], k2, cnt[k2]}
	}

	a := f(0)
	b := f(1)
	n := len(nums)
	if a[0] != b[0] {
		return n - (a[1] + b[1])
	}
	return n - max(a[1]+b[3], a[3]+b[1])
}

力扣原题 · Doocs 题解来源

2171. 拿出最少数目的魔法豆

中等1 种解法

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

题目、示例与约束

给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中拿出一些豆子（也可以 不拿出），使得剩下的非空袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目。

示例 1：

输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2：

输入：beans = [2,10,3,2]
输出：7
解释：
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示：

1 <= beans.length <= 10⁵
1 <= beans[i] <= 10⁵

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

思考

每个非空袋最终豆子数必须相同，可把某袋倒空或减少。等价于选定最终值 $x$ ，把小于 $x$ 的袋清空、把大于 $x$ 的袋减到 $x$ 。 $x$ 只可能取某个原袋的豆子数，否则还可增大 $x$ 而不增加清空代价。

排序后枚举 $beans [i]$ 作为 $x$ ，留下 $(n - i) x$ 颗，拿出 $s - (n - i) x$ 颗。

取该值的最小值。

我们可以将所有袋子中的魔法豆按照从小到大的顺序排列，然后枚举每个袋子的魔法豆数目 $b e a n s [i]$ 作为最终袋子中魔法豆数目，那么一共剩余的魔法豆数目为 $b e a n s [i] \times (n - i)$ ，因此需要拿出的魔法豆数目为 $s - b e a n s [i] \times (n - i)$ ，其中 $s$ 为所有袋子中魔法豆的总数。我们求出所有方案中需要拿出的魔法豆数目的最小值即可。

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

func minimumRemoval(beans []int) int64 {
	sort.Ints(beans)
	s := 0
	for _, x := range beans {
		s += x
	}
	ans := s
	n := len(beans)
	for i, x := range beans {
		ans = min(ans, s-x*(n-i))
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2182. 构造限制重复的字符串

中等1 种解法

标签：贪心、哈希表、字符串、计数、堆（优先队列）

题目、示例与约束

给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母连续出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

示例 1：

输入：s = "cczazcc", repeatLimit = 3
输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。

示例 2：

输入：s = "aababab", repeatLimit = 2
输出："bbabaa"
解释：
使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。 
字母 'a' 连续出现至多 2 次。 
字母 'b' 连续出现至多 2 次。 
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。 
该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。 
注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。

提示：

1 <= repeatLimit <= s.length <= 10⁵
s 由小写英文字母组成

方法一：贪心 · Go 实现

思考

要用完尽可能多、字典序尽可能大的字符，且同一字符不能连续超过 $repeatLimit$ 次。应优先放当前剩余最多的最大字母，放满限额后再插入一个次大字母隔开。

计数 $26$ 个字母，从 z 向 a 扫描；指针 $j$ 指向严格更小且仍有剩余的字母。每次先放 $i$ 至多 $repeatLimit$ 个，若 $i$ 仍剩则夹一个 $j$ 。

$j$ 单调左移，总代价与串长及字母表成线性。

我们先用一个长度为 $26$ 的数组 $c n t$ 统计字符串 $s$ 中每个字符出现的次数，然后从大到小枚举字母表的第 $i$ 个字母，每次取出最多 $min (c n t [i], r e p e a t L i m i t)$ 个字母 $i$ ，如果取完后 $c n t [i]$ 还大于 $0$ ，则继续取字母表中第 $j$ 个字母，其中 $j$ 是最大的满足 $j < i$ 且 $c n t [j] > 0$ 的下标，直到取完所有字母。

时间复杂度 $O (n + | Σ |)$ ，空间复杂度 $O (| Σ |)$ 。其中 $n$ 是字符串 $s$ 的长度，而 $Σ$ 是字符集，本题中 $| Σ | = 26$ 。

func repeatLimitedString(s string, repeatLimit int) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	var ans []byte
	for i, j := 25, 24; i >= 0; i-- {
		j = min(j, i-1)
		for {
			for k := min(cnt[i], repeatLimit); k > 0; k-- {
				ans = append(ans, byte(i+'a'))
				cnt[i]--
			}
			if cnt[i] == 0 {
				break
			}
			for j >= 0 && cnt[j] == 0 {
				j--
			}
			if j < 0 {
				break
			}
			ans = append(ans, byte(j+'a'))
			cnt[j]--
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

2195. 向数组中追加 K 个整数

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个未出现在 nums 中的、互不相同 的正整数，并使结果数组的元素和最小。

返回追加到 nums 中的 k 个整数之和。

示例 1：

输入：nums = [1,4,25,10,25], k = 2
输出：5
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。

示例 2：

输入：nums = [5,6], k = 6
输出：25
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。
nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁹

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

思考

在正整数中选出 $k$ 个未出现在 $nums$ 里的数，使其和最小。应取最小的 $k$ 个缺失正整数。若从 $1$ 起逐个判断是否在集合中，当 $k$ 与 $nums$ 中的空洞都很大时循环次数过多。

排序并加上哨兵 $0$ 与 $2 \times 10^{9}$ 后，相邻值 $(a, b)$ 之间有一段连续缺失。取其中前 $min (k, b - a - 1)$ 个数，其和为等差数列，一次 $O (1)$ 加入答案。

从左到右消耗 $k$ 即可。

我们不妨向数组中加入两个哨兵节点，分别为 $0$ 和 $2 \times 10^{9}$ 。

然后我们对数组进行排序，那么对于数组中的任意两个相邻的元素 $a$ 和 $b$ ，区间 $[a + 1, b - 1]$ 中的整数都是未出现在数组中的，我们可以将这些整数加入到数组中。

因此，我们从小到大遍历数组中的相邻元素对 $(a, b)$ ，对于每个相邻元素对，我们计算区间 $[a + 1, b - 1]$ 中的整数个数 $m$ ，那么这 $m$ 个整数的和为 $\frac{m \times (a + 1 + a + m)}{2}$ ，我们将这个和累加到答案中，并将 $k$ 减去 $m$ 。如果 $k$ 减到 $0$ ，我们就可以停止遍历了，返回答案。

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

func minimalKSum(nums []int, k int) (ans int64) {
	nums = append(nums, []int{0, 2e9}...)
	sort.Ints(nums)
	for i, b := range nums[1:] {
		a := nums[i]
		m := max(0, min(k, b-a-1))
		ans += int64(a+1+a+m) * int64(m) / 2
		k -= m
	}
	return ans
}

力扣原题 · Doocs 题解来源

2202. K 次操作后最大化顶端元素

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，它表示一个堆，其中 nums[0] 是堆顶的元素。

每一次操作中，你可以执行以下操作之一：

如果堆非空，那么删除堆顶端的元素。
如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加回堆顶，这个元素成为新的堆顶元素。

同时给你一个整数 k ，它表示你总共需要执行操作的次数。

请你返回恰好执行 k 次操作以后，堆顶元素的 最大值 。如果执行完 k 次操作以后，堆一定为空，请你返回 -1 。

示例 1：

输入：nums = [5,2,2,4,0,6], k = 4
输出：5
解释：
4 次操作后，堆顶元素为 5 的方法之一为：
- 第 1 次操作：删除堆顶元素 5 ，堆变为 [2,2,4,0,6] 。
- 第 2 次操作：删除堆顶元素 2 ，堆变为 [2,4,0,6] 。
- 第 3 次操作：删除堆顶元素 2 ，堆变为 [4,0,6] 。
- 第 4 次操作：将 5 添加回堆顶，堆变为 [5,4,0,6] 。
注意，这不是最后堆顶元素为 5 的唯一方式。但可以证明，4 次操作以后 5 是能得到的最大堆顶元素。

示例 2：

输入：nums = [2], k = 1
输出：-1
解释：
第 1 次操作中，我们唯一的选择是将堆顶元素弹出堆。
由于 1 次操作后无法得到一个非空的堆，所以我们返回 -1 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i], k <= 10⁹

方法一 · Go 实现

思考

每次操作只能弹出栈顶或把先前弹出的某一元素放回顶部， $k$ 可达 $10^{9}$ ，按步模拟不可行。需要把「恰好 $k$ 次操作后的栈顶」收成几种可比较的情况。

$k = 0$ 时栈顶即为 $n u m s [0]$ 。若数组只有一个元素，奇数次操作会把唯一元素弹出且无法放回，答案为 $- 1$ ；偶数次则仍是该元素。

长度至少为 $2$ 时，前 $k - 1$ 次弹出腾出的数都可以在第 $k$ 次放回成为栈顶，故候选为 $n u m s [0. . k - 2]$ 的最大值；若 $k < n$ ，也可以第 $k$ 次继续弹出，使 $n u m s [k]$ 暴露为栈顶。二者取较大值即可。

func maximumTop(nums []int, k int) int {
	if k == 0 {
		return nums[0]
	}
	n := len(nums)
	if n == 1 {
		if k%2 == 1 {
			return -1
		}
		return nums[0]
	}
	ans := -1
	for i := 0; i < min(k-1, n); i++ {
		ans = max(ans, nums[i])
	}
	if k < n {
		ans = max(ans, nums[k])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2207. 字符串中最多数目的子序列

中等1 种解法

标签：贪心、字符串、前缀和

题目、示例与约束

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。

你可以在 text 中任意位置插入一个字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。

请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。

子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

示例 1：

输入：text = "abdcdbc", pattern = "ac"
输出：4
解释：
如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a' ，那么我们得到 "abadcdbc" 。那么 "ac" 作为子序列出现 4 次。
其他得到 4 个 "ac" 子序列的方案还有 "aabdcdbc" 和 "abdacdbc" 。
但是，"abdcadbc" ，"abdccdbc" 和 "abdcdbcc" 这些字符串虽然是可行的插入方案，但是只出现了 3 次 "ac" 子序列，所以不是最优解。
可以证明插入一个字符后，无法得到超过 4 个 "ac" 子序列。

示例 2：

输入：text = "aabb", pattern = "ab"
输出：6
解释：
可以得到 6 个 "ab" 子序列的部分方案为 "aaabb" ，"aaabb" 和 "aabbb" 。

提示：

1 <= text.length <= 10⁵
pattern.length == 2
text 和 pattern 都只包含小写英文字母。

方法一：遍历 + 计数 · Go 实现

思考

可在 $t e x t$ 任意位置插入一个 $p a t t e r n$ 中的字符，使作为子序列出现的 $p a t t e r n$ 尽量多。 $| t e x t | \leq 10^{5}$ ，不能对每个插入位置重新统计子序列个数。

不插入时，从左扫描即可： $x$ 记下已出现的 $p a t t e r n [0]$ ，每遇到 $p a t t e r n [1]$ 就累加 $x$ 。插入一次后，新增的子序列只可能来自「多一个前缀字符」或「多一个后缀字符」：插在最前则新增量为现有 $p a t t e r n [1]$ 的个数，插在最后则新增量为现有 $p a t t e r n [0]$ 的个数。

因此一遍扫描同时得到不插入的答案以及 $x$ 、 $y$ ，最后再把 $max (x, y)$ 加上即可。注意两个字符相同时，判断顺序要先结算 $p a t t e r n [1]$ 再增加 $x$ ，以免把当前位置与自身配对。

我们可以使用两个变量 $x$ 和 $y$ 分别记录当前字符串中 $pattern [0]$ 和 $pattern [1]$ 出现的次数。

然后遍历字符串 $text$ ，对于当前遍历到的字符 $c$ ：

如果 $c$ 等于 $pattern [1]$ ，我们将 $y$ 加一，此时之前出现过的所有 $pattern [0]$ 都可以和当前的 $c$ 组成一个 $pattern$ 子序列，因此答案加上 $x$ ；
如果 $c$ 等于 $pattern [0]$ ，我们将 $x$ 加一。

遍历结束后，由于我们可以插入一个字符，因此，如果我们在字符串开头加上 $pattern [0]$ ，那么可以得到 $y$ 个 $pattern$ 子序列；如果我们在字符串结尾加上 $pattern [1]$ ，那么可以得到 $x$ 个 $pattern$ 子序列。因此，我们将答案加上 $x$ 和 $y$ 中的较大值即可。

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

func maximumSubsequenceCount(text string, pattern string) (ans int64) {
	x, y := 0, 0
	for _, c := range text {
		if byte(c) == pattern[1] {
			y++
			ans += int64(x)
		}
		if byte(c) == pattern[0] {
			x++
		}
	}
	ans += int64(max(x, y))
	return
}

力扣原题 · Doocs 题解来源

2208. 将数组和减半的最少操作次数

中等1 种解法

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

题目、示例与约束

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择任意一个数并将它减小到恰好一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和至少减少一半的最少操作数。

示例 1：

输入：nums = [5,19,8,1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

示例 2：

输入：nums = [3,8,20]
输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 15.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁷

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

思考

每次把一个数减半，要使总和降到不超过原来的一半，操作次数尽量少。 $n \leq 10^{5}$ ，不能搜索操作序列。减半对总和的贡献等于被选中的那个数的一半，因此每一步都应选当前最大的数。

用大根堆维护全部数值，预先记下需要削减的总量 $s = sum (n u m s) / 2$ 。反复取出堆顶 $t$ ，从 $s$ 中减去 $t / 2$ ，再把 $t / 2$ 放回堆中，直到 $s \leq 0$ 。操作次数即为答案。

根据题目描述，每一次操作，都会将数组中的一个数减半。要使得数组和至少减少一半的操作次数最少，那么每一次操作都应该选择当前数组中的最大值进行减半。

因此，我们先算出数组要减少的总和 $s$ ，然后用一个优先队列（大根堆）维护数组中的所有数，每次从优先队列中取出最大值 $t$ ，将其减半，然后将减半后的数重新放入优先队列中，同时更新 $s$ ，直到 $s \leq 0$ 为止。那么此时的操作次数就是答案。

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

func halveArray(nums []int) (ans int) {
	var s float64
	pq := &hp{}
	for _, x := range nums {
		s += float64(x)
		heap.Push(pq, float64(x))
	}
	s /= 2
	for s > 0 {
		t := heap.Pop(pq).(float64) / 2
		s -= t
		ans++
		heap.Push(pq, t)
	}
	return
}

type hp struct{ sort.Float64Slice }

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

力扣原题 · Doocs 题解来源

2214. 通关游戏所需的最低生命值 🔒

中等1 种解法

标签：贪心、数组

题目、示例与约束

你正在玩一个有 n 个关卡的游戏，从 0 到 n - 1。给你一个 下标从 0 开始 的整数数组 damage，其中 damage[i] 是你完成第 i 个关卡所损失的生命值。

你也会得到一个整数 armor。你最多只能在任何关卡使用一次护甲技能，这将保护你免受最多 armor 伤害。

你必须按顺序完成关卡，并且你的生命值必须一直大于 0 才能通关。

返回你开始通关所需的最低生命值。

示例 1:

输入: damage = [2,7,4,3], armor = 4
输出: 13
解释: 从 13 生命值开始通关游戏的最佳方法是:
第 1 回合，受到 2 点伤害。你还有 13 - 2 = 11 生命值。
第 2 回合，受到 7 点伤害。你还有 11 - 7 = 4 生命值。
第 3 回合，使用你的护甲保护你免受 4 点伤害。你有 4 - 0 = 4 生命值。
第 4 回合，受到 3 点伤害。你还有 4 - 3 = 1 生命值。
注意，13 是你开始时通关游戏所需的最低生命值。

示例 2:

输入: damage = [2,5,3,4], armor = 7
输出: 10
解释: 从 10 生命值开始通关游戏的最佳方法是:
第 1 回合，受到 2 点伤害。你还有 10 - 2 = 8 生命值。
第 2 回合，使用护甲保护自己免受 5 点伤害。你还有 8 - 0 = 8 生命值。
第 3 回合，受到 3 点伤害。你还有 8 - 3 = 5 生命值。
第 4 回合，受到 4 点伤害。你还有 5 - 4 = 1 生命值。
注意，10 是你开始通关所需的最低生命值。

示例 3:

输入: damage = [3,3,3], armor = 0
输出: 10
解释: 从 10 生命值开始通关游戏的最佳方法是:
第 1 回合，受到 2 点伤害。你还有 10 - 3 = 7 生命值。
第 2 回合，受到 3 点伤害。你还有 7 - 3 = 4 生命值。
第 3 回合， 受到 3 点伤害。你还有 4 - 3 = 1 生命值。
注意你没有使用护甲技能。

提示:

n == damage.length
1 <= n <= 10⁵
0 <= damage[i] <= 10⁵
0 <= armor <= 10⁵

方法一：贪心 · Go 实现

思考

按顺序承受全部伤害，生命必须在每一回合后仍为正；护甲只能用在一回合，把该回合伤害变为 $max (0, d - armor)$ 。若枚举护甲用在哪一回合，需要 $O (n)$ 次前缀比较， $n$ 可以接受，但结论可以一次求出。

不使用护甲时，所需生命为全部伤害之和再加 $1$ 。护甲能减免的量不超过自身耐久，也不超过该回合伤害，因此减免上限是 $min (max (damage), armor)$ 。把它用在伤害最大的那一回合，即可少准备这么多生命。

我们可以贪心地选择在伤害值最大的回合中使用一次护甲技能，假设伤害值最大为 $mx$ ，那么我们可以免受 $min (mx, armor)$ 的伤害，因此我们需要的最小生命值为 $\sum (damage) - min (mx, armor) + 1$ 。

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

func minimumHealth(damage []int, armor int) int64 {
	var s int64
	var mx int
	for _, v := range damage {
		s += int64(v)
		mx = max(mx, v)
	}
	return s - int64(min(mx, armor)) + 1
}

力扣原题 · Doocs 题解来源

2216. 美化数组的最少删除数

中等2 种解法

标签：栈、贪心、数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：

nums.length 为偶数
对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立

注意，空数组同样认为是美丽数组。

你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持不变。

返回使 nums 变为美丽数组所需删除的最少元素数目。

示例 1：

输入：nums = [1,1,2,3,5]
输出：1
解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。

示例 2：

输入：nums = [1,1,2,2,3,3]
输出：2
解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

方法一：贪心 · Go 实现

思考

美丽数组要求长度为偶数，且每个偶数下标与其后一位不相等。 $n \leq 10^{5}$ ，不能搜索删哪些位置。从左到右配对时，一旦 $n u m s [i] = n u m s [i + 1]$ ，这一对无法保留，必须删掉其中一个。

贪心删掉当前这个 $n u m s [i]$ ，让后面的元素前移再试，等价于指针只前进一位并计一次删除；若二者不同则这一对合法，指针跳过两位。扫完后若剩余长度仍为奇数，再删一个尾元素即可。

根据题目描述，我们知道，一个美丽数组有偶数个元素，且如果我们把这个数组中每相邻两个元素划分为一组，那么每一组中的两个元素都不相等。这意味着，组内的元素不能重复，但组与组之间的元素可以重复。

因此，我们考虑从左到右遍历数组，只要遇到相邻两个元素相等，我们就将其中的一个元素删除，即删除数加一；否则，我们可以保留这两个元素。

最后，我们判断删除后的数组长度是否为偶数，如果不是，则说明我们需要再删除一个元素，使得最终的数组长度为偶数。

时间复杂度 $O (n)$ ，其中 $n$ 是数组的长度。我们只需要遍历数组一次。空间复杂度 $O (1)$ 。

func minDeletion(nums []int) (ans int) {
	n := len(nums)
	for i := 0; i < n-1; i++ {
		if nums[i] == nums[i+1] {
			ans++
		} else {
			i++
		}
	}
	ans += (n - ans) % 2
	return
}

方法二 · Go 实现

思考

方法一按相邻两项决定是否删除，指针一次走一或两步。也可以先把与 $n u m s [i]$ 相同的连续段压掉：段内多出的元素都必须删，只留下一个作为偶数位，再与段后第一个不同值配成一对。

内层循环跳过相等元素并累计删除，然后指针再跨过配对的后一项。收尾同样按剩余奇偶补删一次。时间仍是 $O (n)$ ，只是按相等段推进。

func minDeletion(nums []int) (ans int) {
	n := len(nums)
	for i := 0; i < n; {
		j := i + 1
		for ; j < n && nums[j] == nums[i]; j++ {
			ans++
		}
		i = j + 1
	}
	ans += (n - ans) % 2
	return
}

力扣原题 · Doocs 题解来源

2224. 转化时间需要的最少操作数

简单1 种解法

标签：贪心、字符串

题目、示例与约束

给你两个字符串 current 和 correct ，表示两个 24 小时制时间 。

24 小时制时间 按 "HH:MM" 进行格式化，其中 HH 在 00 和 23 之间，而 MM 在 00 和 59 之间。最早的 24 小时制时间为 00:00 ，最晚的是 23:59 。

在一步操作中，你可以将 current 这个时间增加 1、5、15 或 60 分钟。你可以执行这一操作任意次数。

返回将 current 转化为 correct 需要的 最少操作数 。

示例 1：

输入：current = "02:30", correct = "04:35"
输出：3
解释：
可以按下述 3 步操作将 current 转换为 correct ：
- 为 current 加 60 分钟，current 变为 "03:30" 。
- 为 current 加 60 分钟，current 变为 "04:30" 。 
- 为 current 加 5 分钟，current 变为 "04:35" 。
可以证明，无法用少于 3 步操作将 current 转化为 correct 。

示例 2：

输入：current = "11:00", correct = "11:01"
输出：1
解释：只需要为 current 加一分钟，所以最小操作数是 1 。

提示：

current 和 correct 都符合 "HH:MM" 格式
current <= correct

方法一：贪心 · Go 实现

思考

每次可把当前时间增加 $1$ 、 $5$ 、 $15$ 或 $60$ 分钟，从 $c u r r e n t$ 加到 $c o r r e c t$ ，次数尽量少。时间差至多不到一天，完全背包式搜索可以，但四种面额能凑出任意正整数，且大面额总是不亏。

先把两个时刻换成从零点起的分钟数，得到正差值 $d$ 。再按 $60$ 、 $15$ 、 $5$ 、 $1$ 依次取尽可能多的步，余数交给更小面额。这与用最少硬币找零在面额整除链上的贪心相同。

func convertTime(current string, correct string) int {
	parse := func(s string) int {
		h := int(s[0]-'0')*10 + int(s[1]-'0')
		m := int(s[3]-'0')*10 + int(s[4]-'0')
		return h*60 + m
	}
	a, b := parse(current), parse(correct)
	ans, d := 0, b-a
	for _, i := range []int{60, 15, 5, 1} {
		ans += d / i
		d %= i
	}
	return ans
}

力扣原题 · Doocs 题解来源

2233. K 次增加后的最大乘积

中等1 种解法

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

题目、示例与约束

给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中任一元素并将它增加 1 。

请你返回至多 k 次操作后，能得到的 nums的 最大乘积 。由于答案可能很大，请你将答案对 10⁹ + 7 取余后返回。

示例 1：

输入：nums = [0,4], k = 5
输出：20
解释：将第一个数增加 5 次。
得到 nums = [5, 4] ，乘积为 5 * 4 = 20 。
可以证明 20 是能得到的最大乘积，所以我们返回 20 。
存在其他增加 nums 的方法，也能得到最大乘积。

示例 2：

输入：nums = [6,3,3,2], k = 2
输出：216
解释：将第二个数增加 1 次，将第四个数增加 1 次。
得到 nums = [6, 4, 3, 3] ，乘积为 6 * 4 * 3 * 3 = 216 。
可以证明 216 是能得到的最大乘积，所以我们返回 216 。
存在其他增加 nums 的方法，也能得到最大乘积。

提示：

1 <= nums.length, k <= 10⁵
0 <= nums[i] <= 10⁶

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

思考

每次把某个元素加一，做 $k$ 次后乘积最大。 $n, k \leq 10^{5}$ ，不能搜索加在哪些位置。对乘积而言，把增量给当前最小的数收益最大：在正数上， $\frac{x + 1}{x}$ 随 $x$ 递减。

用小根堆维护数组，每次取出堆顶加一后放回，重复 $k$ 次，最后把堆中所有数乘起来取模。 $0$ 会被优先加一，从而避免整段乘积为 $0$ 。

根据题目描述，要使得乘积最大，我们需要尽量增大较小的数，因此我们可以使用小根堆来维护数组 $nums$ 。每次从小根堆中取出最小的数，将其增加 $1$ ，然后重新放回小根堆中。重复这个过程 $k$ 次后，我们将当前小根堆中的所有数相乘，即可得到答案。

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

func maximumProduct(nums []int, k int) int {
	h := hp{nums}
	for heap.Init(&h); k > 0; k-- {
		h.IntSlice[0]++
		heap.Fix(&h, 0)
	}
	ans := 1
	for _, x := range nums {
		ans = (ans * x) % (1e9 + 7)
	}
	return ans
}

type hp struct{ sort.IntSlice }

func (hp) Push(any)     {}
func (hp) Pop() (_ any) { return }

力扣原题 · Doocs 题解来源

2234. 花园的最大总美丽值

困难1 种解法

标签：贪心、数组、双指针、二分查找、枚举、前缀和、排序

题目、示例与约束

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花不能移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。

如果一个花园有至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之和：

完善花园数目乘以 full.
剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

请你返回 Alice 种最多 newFlowers 朵花以后，能得到的最大总美丽值。

示例 1：

输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
输出：14
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花
花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。
只有 1 个花园是完善的。
不完善花园里花的最少数目是 2 。
所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。
没有其他方案可以让花园总美丽值超过 14 。

示例 2：

输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
输出：30
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花
花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。
有 3 个花园是完善的。
不完善花园里花的最少数目为 4 。
所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。
没有其他方案可以让花园总美丽值超过 30 。
注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。

提示：

1 <= flowers.length <= 10⁵
1 <= flowers[i], target <= 10⁵
1 <= newFlowers <= 10¹⁰
1 <= full, partial <= 10⁵

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

思考

每种花园要么补到 $target$ 成为完善花园，要么把不完善花园的最小值尽量抬高。 $n \leq 10^{5}$ ，新花数量达 $10^{10}$ ，不能模拟每一朵。完善花园的个数确定后，剩余花朵应全部用于垫高一段最小前缀。

先排序并做前缀和。从已有的完善花园数起，枚举最终完善个数 $x$ ，扣掉补齐最贵的那几座所需的花。剩余花在未完善前缀上二分：把前 $l + 1$ 座都抬到 $f l o w e r s [l]$ 的代价为 $f l o w e r s [l] \cdot (l + 1) - s [l + 1]$ ，再把多出的花均分，但不超过 $target - 1$ 。 $x \cdot full + y \cdot partial$ 取最大。

我们注意到，如果一个花园中种的花的数目已经大于等于 $target$ ，那么这个花园就已经是完善的花园，不能再改变。而不完善的花园中，可以通过种更多的花来使得这个花园变成完善的花园。

我们不妨枚举有多少个花园最终成为完善的花园，假设初始时有 $x$ 个完善的花园，那么我们可以在 $[x, n]$ 范围内枚举。我们应该选择哪些不完善花园变成完善花园呢？实际上，我们应该选择那么花的数目较多的花园，这样才能使得最终剩下的可额外种植的花更多，将这些花用于提升不完善花园的最小值。因此，我们对数组 $flowers$ 进行排序。

接下来，我们枚举完善花园的数目 $x$ ，那么当前要变成完善花园的是 $target [n - x]$ ，需要种植的花的数量为 $max (0, target - flowers [n - x])$ 。

我们更新剩余可种植的花 $newFlowers$ ，如果小于 $0$ ，说明已经不能将更多的花园变成完善花园了，直接退出枚举。

否则，我们在 $[0, . . n - x - 1]$ 范围内，二分查找可以把不完善花园变成完善花园的最大下标。记下标为 $l$ ，那么所需要种植的花的数量为 $cost = flowers [l] \times (l + 1) - s [l + 1]$ ，其中 $s [i]$ 是 $flowers$ 数组中前 $i$ 个数之和。如果此时还能提升最小值的大小，我们算出能提升的幅度 $\frac{newFlowers - cost}{l + 1}$ ，并且保证最终的最小值不超过 $target - 1$ 。即最小值 $y = min (flowers [l] + \frac{newFlowers - cost}{l + 1}, target - 1)$ 。那么此时花园的美丽值为 $x \times full + y \times partial$ 。答案为所有美丽值的最大值。

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

func maximumBeauty(flowers []int, newFlowers int64, target int, full int, partial int) int64 {
	sort.Ints(flowers)
	n := len(flowers)
	s := make([]int, n+1)
	for i, x := range flowers {
		s[i+1] = s[i] + x
	}
	ans := 0
	i := n - sort.SearchInts(flowers, target)
	for x := i; x <= n; x++ {
		if x > 0 {
			newFlowers -= int64(max(target-flowers[n-x], 0))
		}
		if newFlowers < 0 {
			break
		}
		l, r := 0, n-x-1
		for l < r {
			mid := (l + r + 1) >> 1
			if int64(flowers[mid]*(mid+1)-s[mid+1]) <= newFlowers {
				l = mid
			} else {
				r = mid - 1
			}
		}
		y := 0
		if r != -1 {
			cost := flowers[l]*(l+1) - s[l+1]
			y = min(flowers[l]+int((newFlowers-int64(cost))/int64(l+1)), target-1)
		}
		ans = max(ans, x*full+y*partial)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2244. 完成所有任务需要的最少轮数

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。

返回完成所有任务需要的最少轮数，如果无法完成所有任务，返回 -1 。

示例 1：

输入：tasks = [2,2,3,3,2,4,4,4,4,4]
输出：4
解释：要想完成所有任务，一个可能的计划是：
- 第一轮，完成难度级别为 2 的 3 个任务。 
- 第二轮，完成难度级别为 3 的 2 个任务。 
- 第三轮，完成难度级别为 4 的 3 个任务。 
- 第四轮，完成难度级别为 4 的 2 个任务。 
可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。

示例 2：

输入：tasks = [2,3,3]
输出：-1
解释：难度级别为 2 的任务只有 1 个，但每一轮执行中，只能选择完成 2 个或者 3 个相同难度级别的任务。因此，无法完成所有任务，答案为 -1 。

提示：

1 <= tasks.length <= 10⁵
1 <= tasks[i] <= 10⁹

方法一：哈希表 · Go 实现

思考

每轮只能完成 $2$ 或 $3$ 个相同难度的任务，求最少轮数。不同难度互不影响，先按难度计数。某个难度出现 $1$ 次则无法完成。

出现 $v \geq 2$ 次时，应尽量每轮做 $3$ 个： $⌊ v / 3 ⌋$ 轮，若有余数再加一轮（余 $1$ 时把一组 $3$ 拆成两个 $2$ ）。对各难度求和。

我们用哈希表统计每个难度级别的任务数量，然后遍历哈希表，对于每个难度级别的任务数量，如果数量为 $1$ ，则无法完成所有任务，返回 $- 1$ ；否则，计算完成该难度级别的任务需要的轮数，累加到答案中。

最后返回答案即可。

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

func minimumRounds(tasks []int) int {
	cnt := map[int]int{}
	for _, t := range tasks {
		cnt[t]++
	}
	ans := 0
	for _, v := range cnt {
		if v == 1 {
			return -1
		}
		ans += v / 3
		if v%3 != 0 {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2259. 移除指定数字得到的最大结果

简单2 种解法

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

题目、示例与约束

给你一个表示某个正整数的字符串 number 和一个字符 digit 。

从 number 中恰好移除一个等于 digit 的字符后，找出并返回按 十进制 表示最大的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。

示例 1：

输入：number = "123", digit = '3'
输出："12"
解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。

示例 2：

输入：number = "1231", digit = '1'
输出："231"
解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ，返回 "231" 。

示例 3：

输入：number = "551", digit = '5'
输出："51"
解释：可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。

提示：

2 <= number.length <= 100
number 由数字 '1' 到 '9' 组成
digit 是 '1' 到 '9' 中的一个数字
digit 在 number 中出现至少一次

方法一：暴力枚举 · Go 实现

思考

必须删去恰好一个给定数字，使剩下的十进制串最大。长度不超过 $100$ ，每种删除位置拼出新串再取最大即可。

枚举所有等于 $digit$ 的下标 $i$ ，比较 $n u m b e r [: i] + n u m b e r [i + 1 :]$ 。字符串比较与数值比较一致。

我们可以枚举字符串 $number$ 的所有位置 $i$ ，如果 $number [i] = digit$ ，那么我们取 $number$ 的前缀 $number [0 : i]$ 和后缀 $number [i + 1 :]$ 拼接起来，即为移除 $number [i]$ 后的结果。我们取所有可能的结果中最大的即可。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $number$ 的长度。

func removeDigit(number string, digit byte) string {
	ans := "0"
	for i, d := range number {
		if d == rune(digit) {
			t := number[:i] + number[i+1:]
			if strings.Compare(ans, t) < 0 {
				ans = t
			}
		}
	}
	return ans
}

方法二：贪心 · Go 实现

思考

方法一要生成并比较多段字符串。从左到右看，若某次出现的 $digit$ 小于它的下一位，删掉它会立刻让高位变大，这就是最优。若不存在这样的下降，则删最后一次出现，以免高位变小。

一遍记下最后位置 $l a s t$ ，遇到 $d < n u m b e r [i + 1]$ 即可提前结束。时间降为线性。

我们可以枚举字符串 $number$ 的所有位置 $i$ ，如果 $number [i] = digit$ ，记录 $digit$ 最后一次出现的位置 $last$ ，并且如果 $i + 1 < n$ 且 $number [i] < number [i + 1]$ ，那么我们可以直接返回 $number [0 : i] + number [i + 1 :]$ ，即为移除 $number [i]$ 后的结果。这是因为如果 $number [i] < number [i + 1]$ ，那么移除 $number [i]$ 后，结果一定会更大。

遍历结束，我们返回 $number [0 : last] + number [last + 1 :]$ 即可。

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

func removeDigit(number string, digit byte) string {
	last := -1
	n := len(number)
	for i := range number {
		if number[i] == digit {
			last = i
			if i+1 < n && number[i] < number[i+1] {
				break
			}
		}
	}
	return number[:last] + number[last+1:]
}

力扣原题 · Doocs 题解来源

2268. 最少按键次数 🔒

中等1 种解法

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

题目、示例与约束

你有一个 9 键键盘，按键按 1 到 9 编号，每个按键对应着几个英文小写字母。你可以决定每个按键对应哪些英文字母，但要满足如下条件：

26 个英文小写字母必须全部映射到这 9 个按键上。
每个英文字母只能映射到恰好一个按键上。
每个按键最多对应 3 个英文字母。

如果想打出按键上的第一个字母，只需要按一次。如果想打出按键上的第二个字母，则需要按两次，依次类推。

给你一个字符串 s ，返回基于你设计的键盘打出 s 需要的最少按键次数。

注意：字母映射到每个按键上，映射的顺序无法进行更改。

示例 1 ：

输入：s = "apple"
输出：5
解释：上图所示为设置键盘的最佳方法之一。
按按键 1 一次输入 'a' 。
按按键 6 一次输入 'p' 。
按按键 6 一次输入 'p' 。
按按键 5 一次输入 'l' 。
按按键 3 一次输入 'e' 。
总共按按键 5 次，所以返回 5 。

示例 2 ：

输入：s = "abcdefghijkl"
输出：15
解释：上图所示为设置键盘的最佳方法之一。
字母 'a' 到 'i' 每个只需要按一次按键。
按按键 1 两次输入 'j' 。
按按键 2 两次输入 'k' 。
按按键 3 两次输入 'l' 。
总共按按键 15 次，所以返回 15 。

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成

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

思考

九个按键，每个最多映射三个字母，按键次数等于该字母在映射中的位置。 $| s | \leq 10^{5}$ ，应让出现次数多的字母占用靠前的键位。

统计频率后从大到小排列：前 $9$ 个字母各按 $1$ 次，接下来 $9$ 个按 $2$ 次，以此类推。第 $i$ 个频率乘当前层数 $k$ ，每放满 $9$ 个就把 $k$ 加一。

我们首先统计字符串 $s$ 中每个字符出现的次数，记录在数组或者哈希表 $cnt$ 中。

题目要求按键次数最少，那么出现最多的 $9$ 个字符应该对应按键 $1$ 到按键 $9$ ，出现次数第 $10$ 到第 $18$ 多的字符再次对应按键 $1$ 到按键 $9$ ，以此类推。

因此，我们可以将 $cnt$ 中的值按照从大到小的顺序排序，然后按照 $1$ 到 $9$ 的顺序依次分配给按键，每次分配完 $9$ 个字符后，按键次数加 $1$ 。

时间复杂度 $O (n + | Σ | \times \log | Σ |)$ ，空间复杂度 $O (| Σ |)$ 。其中 $n$ 是字符串 $s$ 的长度，而 $Σ$ 是字符串 $s$ 中出现的字符集合，本题中 $Σ$ 是小写字母集合，因此 $| Σ | = 26$ 。

func minimumKeypresses(s string) (ans int) {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	sort.Ints(cnt)
	k := 1
	for i := 1; i <= 26; i++ {
		ans += k * cnt[26-i]
		if i%9 == 0 {
			k++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2271. 毯子覆盖的最多白色砖块数

中等1 种解法

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

题目、示例与约束

给你一个二维整数数组 tiles ，其中 tiles[i] = [l_i, r_i] ，表示所有在 l_i <= j <= r_i 之间的每个瓷砖位置 j 都被涂成了白色。

同时给你一个整数 carpetLen ，表示可以放在 任何位置 的一块毯子的长度。

请你返回使用这块毯子，最多可以盖住多少块白色瓷砖。

示例 1：

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。

示例 2：

输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。

提示：

1 <= tiles.length <= 5 * 10⁴
tiles[i].length == 2
1 <= l_i <= r_i <= 10⁹
1 <= carpetLen <= 10⁹
tiles 互相 不会重叠 。

方法一：贪心 + 排序 + 滑动窗口 · Go 实现

思考

地毯长度为 $carpetLen$ ，砖块是若干互不相交的区间。地毯左端若停在某段中间，覆盖不会优于把它对齐到某一段的左端。因此只需枚举「地毯左端贴在 $t i l e s [i]$ 的左端」。

砖块先按左端排序。指针 $j$ 维护右端仍被整段盖住的最远砖块，并用 $s$ 记下这些整段的白砖数。若下一段被部分盖住，再补上 $l i + carpetLen - t i l e s [j] [0]$ 。 $j$ 只前进，总时间 $O (n \log n)$ 。

直觉上，毯子的左端点一定与某块瓷砖的左端点重合，这样才能使得毯子覆盖的瓷砖最多。

我们可以来简单证明一下。

如果毯子落在某块瓷砖的中间某个位置，将毯子右移一个，毯子覆盖的瓷砖数量可能减少，也可能不变，但不可能增加；将毯子左移一个，毯子覆盖的瓷砖数量可能不变，也可能增加，但不可能减少。

也就是说，将毯子左移至某块瓷砖的左端点，一定可以使得毯子覆盖的瓷砖数量最多。

因此，我们可以将所有瓷砖按照左端点从小到大排序，然后枚举每块瓷砖的左端点，计算出以该左端点为起点的毯子覆盖的瓷砖数量，取最大值即可。

为了计算以某块瓷砖的左端点为起点的毯子覆盖的瓷砖数量，我们可以使用滑动窗口的思想，维护一个右端点不断右移的窗口，窗口内的瓷砖数量即为毯子覆盖的瓷砖数量。

时间复杂度 $O (n \log n)$ ，其中 $n$ 为瓷砖的数量。

func maximumWhiteTiles(tiles [][]int, carpetLen int) int {
	sort.Slice(tiles, func(i, j int) bool { return tiles[i][0] < tiles[j][0] })
	n := len(tiles)
	s, ans := 0, 0
	for i, j := 0, 0; i < n; i++ {
		for j < n && tiles[j][1]-tiles[i][0]+1 <= carpetLen {
			s += tiles[j][1] - tiles[j][0] + 1
			j++
		}
		if j < n && tiles[i][0]+carpetLen > tiles[j][0] {
			ans = max(ans, s+tiles[i][0]+carpetLen-tiles[j][0])
		} else {
			ans = max(ans, s)
		}
		s -= (tiles[i][1] - tiles[i][0] + 1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2279. 装满石头的背包的最大数量

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往任意背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的最大数量。

示例 1：

输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。

示例 2：

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3
解释：
8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。

提示：

n == capacity.length == rocks.length
1 <= n <= 5 * 10⁴
1 <= capacity[i] <= 10⁹
0 <= rocks[i] <= capacity[i]
1 <= additionalRocks <= 10⁹

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

思考

额外石头要尽量装满更多背包。每个背包的缺口独立， $n \leq 5 \times 10^{4}$ ，应优先填缺口小的。

把 $c a p a c i t y [i] - r o c k s [i]$ 排序后从小到大扣除 $additionalRocks$ ，一旦不够就返回已装满的个数。

我们首先将每个背包的剩余容量计算出来，然后对剩余容量进行排序，接着我们从小到大遍历剩余容量，将额外的石头放入背包中，直到额外的石头用完或者背包的剩余容量用完为止，返回此时的背包数量即可。

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

func maximumBags(capacity []int, rocks []int, additionalRocks int) int {
	for i, x := range rocks {
		capacity[i] -= x
	}
	sort.Ints(capacity)
	for i, x := range capacity {
		additionalRocks -= x
		if additionalRocks < 0 {
			return i
		}
	}
	return len(capacity)
}

力扣原题 · Doocs 题解来源

2294. 划分数组使最大差为 K

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都恰好出现在一个子序列中。

在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的最少子序列数目。

子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。

示例 1：

输入：nums = [3,6,1,2,5], k = 2
输出：2
解释：
可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。

示例 2：

输入：nums = [1,2,3], k = 1
输出：2
解释：
可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。

示例 3：

输入：nums = [2,2,4,5], k = 0
输出：3
解释：
可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵
0 <= k <= 10⁵

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

思考

划分的是子序列而非子数组，同一段只需 $max - min \leq k$ 。 $n \leq 10^{5}$ ，应先排序：相邻值最容易放在同一段。一段从当前最小值 $a$ 开始，遇到 $b - a > k$ 就必须新开一段并把 $a$ 换成 $b$ 。

排序后一遍扫描，初始段数为 $1$ 。段数最少，因为每段都尽量向右延伸。

题目要求划分子序列，而不是子数组，因此子序列中的元素可以不连续。我们可以将数组 $nums$ 排序，假设当前子序列的第一个元素为 $a$ ，则子序列中的最大值和最小值的差值不会超过 $k$ 。因此我们可以遍历数组 $nums$ ，如果当前元素 $b$ 与 $a$ 的差值大于 $k$ ，则更新 $a$ 为 $b$ ，并将子序列数目加 1。遍历结束后，即可得到最少子序列数目，注意初始时子序列数目为 $1$ 。

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

func partitionArray(nums []int, k int) int {
	sort.Ints(nums)
	ans, a := 1, nums[0]
	for _, b := range nums {
		if b-a > k {
			a = b
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2323. 完成所有工作的最短时间 II 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你两个 下标从 0 开始 的整数数组 jobs 和相等长度的 workers ，其中 jobs[i]是完成第 i 个工作所需的时间，workers[j] 是第 j 个工人每天可以工作的时间。

每项工作都应该正好分配给一个工人，这样每个工人就只能完成一项工作。

返回分配后完成所有作业所需的最少天数。

示例 1:

输入: jobs = [5,2,4], workers = [1,7,5]
输出: 2
解释:
- 把第 2 个工人分配到第 0 个工作。他们花了 1 天时间完成这项工作。
- 把第 0 个工人分配到第 1 个工作。他们花了 2 天时间完成这项工作。
- 把第 1 个工人分配到第 2 个工作。他们花了 1 天时间完成这项工作。
所有工作完成需要 2 天，因此返回 2。
可以证明 2 天是最少需要的天数。

示例 2:

输入: jobs = [3,18,15,9], workers = [6,5,1,3]
输出: 3
解释:
- 把第 2 个工人分配到第 0 个工作。他花了 3 天时间完成这项工作。
- 把第 0 个工人分配到第 1 个工作。他花了 3 天时间完成这项工作。
- 把第 1 个工人分配到第 2 个工作。他花了 3 天时间完成这项工作。
- 把第 3 个工人分配到第 3 个工作。他花了 3 天时间完成这项工作。
完成所有工作需要 3 天，因此返回 3。
可以证明，3 天是最少需要的天数。

提示:

n == jobs.length == workers.length
1 <= n <= 10⁵
1 <= jobs[i], workers[i] <= 10⁵

方法一：贪心 · Go 实现

思考

每人恰好一份工作，完成时间为 $⌈ j o b s_{i} / w o r k e r s_{j} ⌉$ 的最大值。人数与工作数相同，关键在匹配方式。

较大工作配较慢工人会抬高最大值。将两边同时排序后按下标配对，相当于让更强工人承担更重工作，再取向上取整后的最大值。

为了使得完成所有工作所需的最少天数尽可能小，我们可以尽量让工作时间较长的工人去完成工作时间较长的工作。

因此，我们可以先对 $jobs$ 和 $workers$ 进行排序，然后依次将工作分配给对应下标的工人，求最大的工作时间和工人时间的比值即可。

时间复杂度 $O (n \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 为工作数。

func minimumTime(jobs []int, workers []int) (ans int) {
	sort.Ints(jobs)
	sort.Ints(workers)
	for i, a := range jobs {
		b := workers[i]
		ans = max(ans, (a+b-1)/b)
	}
	return
}

力扣原题 · Doocs 题解来源

2333. 最小差值平方和

中等1 种解法

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

题目、示例与约束

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

数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 <= i < n 的 (nums1[i] - nums2[i])² 之和。

同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -1 至多 k1 次。类似的，你可以将 nums2 中的任意元素 +1 或者 -1 至多 k2 次。

请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小 差值平方和 。

注意：你可以将数组中的元素变成负整数。

示例 1：

输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
输出：579
解释：nums1 和 nums2 中的元素不能修改，因为 k1 = 0 和 k2 = 0 。
差值平方和为：(1 - 2)²+ (2 - 10)²+ (3 - 20)²+ (4 - 19)² = 579 。

示例 2：

输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
输出：43
解释：一种得到最小差值平方和的方式为：
- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。
最小差值平方和为：
(2 - 5)²+ (4 - 8)²+ (10 - 7)²+ (12 - 9)² = 43 。
注意，也有其他方式可以得到最小差值平方和，但没有得到比 43 更小答案的方案。

提示：

n == nums1.length == nums2.length
1 <= n <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁵
0 <= k1, k2 <= 10⁹

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

思考

对任一位置做一次 $\pm 1$ ，无论改的是 $n u m s 1$ 还是 $n u m s 2$ ，都只是把该位置的绝对差值减一，因此 $k_{1}$ 与 $k_{2}$ 可以合成总预算 $k$ 。 $n \leq 10^{5}$ ，预算最高到 $2 \times 10^{9}$ ，按次模拟或用堆维护当前最大值都会超时。

平方严格凸，同一次操作减在更大的差值上，平方和下降更多，所以应当总是削当前最大的差值。差值本身不超过 $10^{5}$ ，相等的差值可以整层下移。

统计每个差值的出现次数后从大到小扫描：预算够覆盖整层，就把这一层全部并入下一层；否则用完剩余预算并停止。所有差值之和不超过 $k$ 时，答案为 $0$ 。

我们令 $k = k_{1} + k_{2}$ ，并计算每个位置的差值 $d_{i} = | n u m s 1_{i} - n u m s 2_{i} |$ 。若这些差值之和不超过 $k$ ，则可以把它们全部降为 $0$ ，答案为 $0$ 。

否则用数组 $c n t$ 记录每个差值出现的次数，记最大差值为 $m$ 。从 $v = m$ 起向下枚举：这一层有 $c n t [v]$ 个数，实际能减一的个数是 $take = min (c n t [v], k)$ 。把这 $take$ 个数挪到 $v - 1$ ，并令 $k$ 减去 $take$ 。 $k$ 用尽后即可停止。

答案等于 $\sum_{v} v^{2} \cdot c n t [v]$ 。

时间复杂度 $O (n + M)$ ，空间复杂度 $O (M)$ 。其中 $n$ 是数组长度， $M$ 是差值的最大值，本题中 $M \leq 10^{5}$ 。

func minSumSquareDiff(nums1 []int, nums2 []int, k1 int, k2 int) int64 {
	k := k1 + k2
	var s int64
	mx := 0
	cnt := make([]int, 100001)
	for i, a := range nums1 {
		v := abs(a - nums2[i])
		cnt[v]++
		s += int64(v)
		mx = max(mx, v)
	}
	if s <= int64(k) {
		return 0
	}
	for v := mx; v > 0 && k > 0; v-- {
		if cnt[v] == 0 {
			continue
		}
		take := min(cnt[v], k)
		k -= take
		cnt[v] -= take
		cnt[v-1] += take
	}
	var ans int64
	for v := 0; v <= mx; v++ {
		ans += int64(v) * int64(v) * int64(cnt[v])
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

2335. 装满杯子需要的最短总时长

简单2 种解法

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

题目、示例与约束

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯不同类型的水或者 1 杯任意类型的水。

给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的最少秒数。

示例 1：

输入：amount = [1,4,2]
输出：4
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。

示例 2：

输入：amount = [5,4,4]
输出：7
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。

示例 3：

输入：amount = [5,0,0]
输出：5
解释：每秒装满一杯冷水。

提示：

amount.length == 3
0 <= amount[i] <= 100

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

思考

每秒可给两种不同杯子各接 $1$ ，或只接一种。总量不超过 $300$ ，反复取当前最多的两杯减一即可。

每次排序后减少最大的两个（第二大已为 $0$ 则只减一个），直到全为 $0$ 。贪心保证每秒尽量消化两份需求。

我们可以每次贪心地选择其中较大的两个数进行减一操作（最多减为 $0$ ），直至所有数变为 $0$ 。

时间复杂度 $O (S)$ ，空间复杂度 $O (1)$ 。其中 $S$ 为数组 amount 中所有数的和，本题中 $S \leq 300$ 。

func fillCups(amount []int) int {
	ans := 0
	for amount[0]+amount[1]+amount[2] > 0 {
		sort.Ints(amount)
		ans++
		amount[2]--
		if amount[1] > 0 {
			amount[1]--
		}
	}
	return ans
}

方法二：贪心 + 分类讨论 · Go 实现

思考

方法一按秒模拟。将三数排序为 $a \leq b \leq c$ 后可闭式求解：若 $a + b \leq c$ ，较短的两杯可在 $c$ 秒内穿插接完；否则总能两两配对，答案为 $⌊ (a + b + c + 1) / 2 ⌋$ 。

我们可以将数组 amount 排序，设 $a$ , $b$ , $c$ 分别为数组 amount 中的三个数，有以下两种情况：

如果 $a + b \leq c$ ，此时我们只需要 $c$ 次操作即可将所有数变为 $0$ ，因此答案为 $c$ 。
如果 $a + b > c$ ，每一次操作我们都可以将其中两个数减一，最终匹配完，或者剩下最后一个数（取决于总和是偶数还是奇数），因此答案为 $⌊ \frac{a + b + c + 1}{2} ⌋$ 。

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

func fillCups(amount []int) int {
	sort.Ints(amount)
	if amount[0]+amount[1] <= amount[2] {
		return amount[2]
	}
	return (amount[0] + amount[1] + amount[2] + 1) / 2
}

力扣原题 · Doocs 题解来源

2340. 生成有效数组的最少交换次数 🔒

中等1 种解法

标签：贪心、数组

题目、示例与约束

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

nums 上的相邻元素可以进行交换。

一个有效的数组必须满足以下条件:

最大的元素 (如果有多个，则为最大元素中的任何一个) 位于数组中最右边的位置。
最小的元素 (如果有多个，则为最小的任何一个元素) 位于数组的最左侧。

返回使 nums 成为有效数组所需的最少交换次数。

示例 1:

输入: nums = [3,4,5,5,3,1]
输出: 6
解释: 进行以下交换:
- 交换 1:交换第 3 和第 4 个元素，然后 nums 是 [3,4,5,3,5,1].
- 交换 2:交换第 4 和第 5 个元素，然后 nums 是 [3,4,5,3,1,5].
- 交换 3:交换第 3 和第 4 个元素，然后 nums 是  [3,4,5,1,3,5].
- 交换 4:交换第 2 和第 3 个元素，然后 nums 是  [3,4,1,5,3,5].
- 交换 5:交换第 1 和第 2 个元素，然后 nums 是  [3,1,4,5,3,5].
- 交换 6:交换第 0 和第 1 个元素，然后 nums 是  [1,3,4,5,3,5].
可以证明，6 次交换是组成一个有效数组所需的最少交换次数。

示例 2:

输入: nums = [9]
输出: 0
解释: 该数组已经有效，因此返回 0。

提示:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

方法一：维护最值下标 + 分类讨论 · Go 实现

思考

只需把全局最小换到最左、全局最大换到最右，且最小取最左出现、最大取最右出现。一次遍历记下这两个下标。

两下标不相交时次数相加；最小值在最大值右侧时，两次移动共用一次交换，答案减一。

我们可以用下标 $i$ 和 $j$ 分别记录数组 $nums$ 第一个最小值和最后一个最大值的下标，遍历数组 $nums$ ，更新 $i$ 和 $j$ 的值。

接下来，我们需要考虑交换的次数。

如果 $i = j$ ，说明数组 $nums$ 已经是有效数组，不需要交换，返回 $0$ ；
如果 $i < j$ ，说明数组 $nums$ 中最小值在最大值的左边，需要交换 $i + n - 1 - j$ 次，其中 $n$ 为数组 $nums$ 的长度；
如果 $i > j$ ，说明数组 $nums$ 中最小值在最大值的右边，需要交换 $i + n - 1 - j - 1$ 次。

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

func minimumSwaps(nums []int) int {
	var i, j int
	for k, v := range nums {
		if v < nums[i] || (v == nums[i] && k < i) {
			i = k
		}
		if v > nums[j] || (v == nums[j] && k > j) {
			j = k
		}
	}
	if i == j {
		return 0
	}
	if i < j {
		return i + len(nums) - 1 - j
	}
	return i + len(nums) - 2 - j
}

力扣原题 · Doocs 题解来源

2350. 不可能得到的最短骰子序列

困难1 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。

请你返回无法从 rolls 中得到的最短骰子子序列的长度。

扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。

注意，子序列只需要保持在原数组中的顺序，不需要连续。

示例 1：

输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4
输出：3
解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。
所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。
子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。
还有别的子序列也无法从原数组中得到。

示例 2：

输入：rolls = [1,1,2,2], k = 2
输出：2
解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。
子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。
还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。

示例 3：

输入：rolls = [1,1,3,2,2,2,3,3], k = 4
输出：1
解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。
还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。

提示：

n == rolls.length
1 <= n <= 10⁵
1 <= rolls[i] <= k <= 10⁵

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

思考

长度为 $L$ 的序列可被 $r o l l s$ 作为子序列取出，当且仅当能依次找到 $L$ 组完整的 $1. . k$ 。 $n \leq 10^{5}$ ，不能枚举序列。

从左到右收集尚未出现的点数；当集合大小达到 $k$ ，说明又完成一轮「任意下一面」，答案加一并清空集合。最终答案是完成轮数加一，即第一段凑不齐的长度。

时间复杂度 $O (n)$ 。

func shortestSequence(rolls []int, k int) int {
	s := map[int]bool{}
	ans := 1
	for _, v := range rolls {
		s[v] = true
		if len(s) == k {
			ans++
			s = map[int]bool{}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2357. 使数组中所有元素都等于零

简单1 种解法

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

题目、示例与约束

给你一个非负整数数组 nums 。在一步操作中，你必须：

选出一个正整数 x ，x 需要小于或等于 nums 中最小的非零元素。
nums 中的每个正整数都减去 x。

返回使 nums 中所有元素都等于 0 需要的最少操作数。

示例 1：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。

示例 2：

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

方法一：哈希表或数组 · Go 实现

思考

每次选一个正数 $x$ 并从所有 $\geq x$ 的元素中减去 $x$ ，等价于消去一种正值。 $n \leq 100$ ，统计不同正数即可。

零不被操作改变，也不产生新的正值种类。答案等于集合 ${x \in n u m s : x > 0}$ 的大小。

我们观察到，每一次操作，都可以把数组 $nums$ 中相同且非零的元素减少到 $0$ ，因此，我们只需要统计数组 $nums$ 中有多少个不同的非零元素，即为最少操作数。统计不同的非零元素，可以使用哈希表或数组来实现。

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

func minimumOperations(nums []int) (ans int) {
	s := [101]bool{true}
	for _, x := range nums {
		if !s[x] {
			s[x] = true
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

LeetCode Go · 贪心（7） ​

2132. 用邮票贴满网格图 ​

2136. 全部开花的最早一天 ​

2139. 得到目标值的最少行动次数 ​

2141. 同时运行 N 台电脑的最长时间 ​

2144. 打折购买糖果的最小开销 ​

2160. 拆分数位后四位数字的最小和 ​

2170. 使数组变成交替数组的最少操作数 ​

2171. 拿出最少数目的魔法豆 ​

2182. 构造限制重复的字符串 ​

2195. 向数组中追加 K 个整数 ​

2202. K 次操作后最大化顶端元素 ​

2207. 字符串中最多数目的子序列 ​

2208. 将数组和减半的最少操作次数 ​

2214. 通关游戏所需的最低生命值 🔒 ​

2216. 美化数组的最少删除数 ​

2224. 转化时间需要的最少操作数 ​

2233. K 次增加后的最大乘积 ​

2234. 花园的最大总美丽值 ​

2244. 完成所有任务需要的最少轮数 ​

2259. 移除指定数字得到的最大结果 ​

2268. 最少按键次数 🔒 ​

2271. 毯子覆盖的最多白色砖块数 ​

2279. 装满石头的背包的最大数量 ​

2294. 划分数组使最大差为 K ​

2323. 完成所有工作的最短时间 II 🔒 ​

2333. 最小差值平方和 ​

2335. 装满杯子需要的最短总时长 ​

2340. 生成有效数组的最少交换次数 🔒 ​

2350. 不可能得到的最短骰子序列 ​

2357. 使数组中所有元素都等于零 ​

继续阅读

LeetCode Go · 贪心（7）

2132. 用邮票贴满网格图

2136. 全部开花的最早一天

2139. 得到目标值的最少行动次数

2141. 同时运行 N 台电脑的最长时间

2144. 打折购买糖果的最小开销

2160. 拆分数位后四位数字的最小和

2170. 使数组变成交替数组的最少操作数

2171. 拿出最少数目的魔法豆

2182. 构造限制重复的字符串

2195. 向数组中追加 K 个整数

2202. K 次操作后最大化顶端元素

2207. 字符串中最多数目的子序列

2208. 将数组和减半的最少操作次数

2214. 通关游戏所需的最低生命值 🔒

2216. 美化数组的最少删除数

2224. 转化时间需要的最少操作数

2233. K 次增加后的最大乘积

2234. 花园的最大总美丽值

2244. 完成所有任务需要的最少轮数

2259. 移除指定数字得到的最大结果

2268. 最少按键次数 🔒

2271. 毯子覆盖的最多白色砖块数

2279. 装满石头的背包的最大数量

2294. 划分数组使最大差为 K

2323. 完成所有工作的最短时间 II 🔒

2333. 最小差值平方和

2335. 装满杯子需要的最短总时长

2340. 生成有效数组的最少交换次数 🔒

2350. 不可能得到的最短骰子序列

2357. 使数组中所有元素都等于零