LeetCode Go · 贪心（2）

来源与许可

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

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

649. Dota2 参议院

中等1 种解法

标签：贪心、队列、字符串

题目、示例与约束

Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

剥夺一名参议员的权利：一名参议员可以使另一名参议员在本轮及所有后续轮次中失去所有权利。
宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。

示例 1：

输入：senate = "RD"
输出："Radiant"
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。

示例 2：

输入：senate = "RDD"
输出："Dire"
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示：

n == senate.length
1 <= n <= 10⁴
senate[i] 为 'R' 或 'D'

方法一：队列 + 模拟 · Go 实现

思考

参议员按顺序行使「禁止下一名对方」的权利，直到一方清空。直接在字符串里反复删人，最坏接近平方。

两队下标分别入队。队首较小者先手，把对方弹出，自己下标加 $n$ 回到队尾表示下一轮。一队空即胜。

我们创建两个队列 $q r$ 和 $q d$ ，分别记录天辉和夜魇阵营的参议员的下标。然后我们开始进行模拟，每一轮各从队首取出一位参议员，然后根据他的阵营进行不同的操作：

如果天辉阵营的参议员编号小于夜魇阵营的参议员编号，那么该天辉阵营的参议员就可以将夜魇阵营的参议员票权永久取消，我们将天辉阵营的参议员的下标加 $n$ 后重新放回队尾，表示该参议员会参与下一轮的投票。
如果夜魇阵营的参议员编号小于天辉阵营的参议员编号，那么该夜魇阵营的参议员就可以将天辉阵营的参议员票权永久取消，我们将夜魇阵营的参议员的下标加 $n$ 后重新放回队尾，表示该参议员会参与下一轮的投票。

最后当队列中只剩一种阵营的参议员时，该阵营的参议员获胜。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为参议员的数量。

func predictPartyVictory(senate string) string {
	n := len(senate)
	qr := []int{}
	qd := []int{}
	for i, c := range senate {
		if c == 'R' {
			qr = append(qr, i)
		} else {
			qd = append(qd, i)
		}
	}
	for len(qr) > 0 && len(qd) > 0 {
		r, d := qr[0], qd[0]
		qr, qd = qr[1:], qd[1:]
		if r < d {
			qr = append(qr, r+n)
		} else {
			qd = append(qd, d+n)
		}
	}
	if len(qr) > 0 {
		return "Radiant"
	}
	return "Dire"
}

力扣原题 · Doocs 题解来源

659. 分割数组为连续子序列

中等1 种解法

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

题目、示例与约束

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述两个条件：

每个子序列都是一个 连续递增序列（即，每个整数恰好比前一个整数大 1 ）。
所有子序列的长度至少为 3 。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

提示：

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000
nums 按非递减顺序排列

方法一：哈希表 + 优先队列（小根堆） · Go 实现

思考

要把数组拆成若干长度至少为 $3$ 的连续递增子序列。贪心「总是开新序列」可能让短序列无法延长。

哈希表把结尾为 $v$ 的各序列长度放进小根堆。当前值优先接到 $v - 1$ 的最短序列上，否则新开长度为 $1$ 的序列。最后堆顶都不小于 $3$ 则可行。

由于题目中的子序列是由连续整数组成的，因此，只要知道子序列的最后一个数以及子序列的长度，就能够确定子序列。

我们可以使用哈希表存储每个子序列的最后一个数，使用优先队列存储当前数作为子序列的末尾时，子序列的长度。我们要优先选择长度较短的子序列，因此使用小根堆。

遍历数组 nums，对于当前遍历到的数 num，如果 num 不能加入到任何子序列中，那么我们就创建一个新的子序列，长度为 1；否则，我们就将 num 加入到某个子序列中，具体的子序列是哪个呢？我们可以从 num - 1 对应的子序列中取出一个长度最短的子序列，将 num 加入到该子序列中，然后将该子序列的最后一个数更新为 num，同时将该子序列的长度加 1。

如果我们遍历完数组 nums，优先队列中所有的子序列的长度都不小于 3，那么我们就可以将数组 nums 分割成若干个子序列，否则，我们就无法将数组 nums 分割成若干个子序列。

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

func isPossible(nums []int) bool {
	d := map[int]*hp{}
	for _, v := range nums {
		if d[v] == nil {
			d[v] = new(hp)
		}
		if h := d[v-1]; h != nil {
			heap.Push(d[v], heap.Pop(h).(int)+1)
			if h.Len() == 0 {
				delete(d, v-1)
			}
		} else {
			heap.Push(d[v], 1)
		}
	}
	for _, q := range d {
		if q.IntSlice[0] < 3 {
			return false
		}
	}
	return true
}

type hp struct{ sort.IntSlice }

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

力扣原题 · Doocs 题解来源

670. 最大交换

中等1 种解法

标签：贪心、数学

题目、示例与约束

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

给定数字的范围是 [0, 10⁸]

方法一：贪心 · Go 实现

思考

至多交换两位使整数最大。枚举所有交换是平方级，位数很少也能更好。

从右往左记下每位右侧最大值下标；再从左往右找第一处 $s [i] < s [d [i]]$ 并交换。高位尽早换成更大数字。

我们先将数字转为字符串 $s$ ，然后从右往左遍历字符串 $s$ ，用数组或哈希表 $d$ 记录每个数字右侧的最大数字的位置（可以是数字本身的位置）。

接着从左到右遍历 $d$ ，如果 $s [i] < s [d [i]]$ ，则进行交换，并退出遍历的过程。

最后将字符串 $s$ 转为数字，即为答案。

时间复杂度 $O (\log M)$ ，空间复杂度 $O (\log M)$ 。其中 $M$ 是数字 $n u m$ 的取值范围。

func maximumSwap(num int) int {
	s := []byte(strconv.Itoa(num))
	n := len(s)
	d := make([]int, n)
	for i := range d {
		d[i] = i
	}
	for i := n - 2; i >= 0; i-- {
		if s[i] <= s[d[i+1]] {
			d[i] = d[i+1]
		}
	}
	for i, j := range d {
		if s[i] < s[j] {
			s[i], s[j] = s[j], s[i]
			break
		}
	}
	ans, _ := strconv.Atoi(string(s))
	return ans
}

力扣原题 · Doocs 题解来源

680. 验证回文串 II

简单1 种解法

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

题目、示例与约束

给你一个字符串 s，最多可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"
输出：false

提示：

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

方法一：双指针 · Go 实现

思考

最多删一个字符使串成为回文。枚举删除位置再检查是平方级， $n$ 可达 $10^{5}$ 。

两端指针相遇前若失配，只需再验证「删左」或「删右」两段是否回文。至多一次分歧，整体仍线性。

我们用两个指针分别指向字符串的左右两端，每次判断两个指针指向的字符是否相同，如果不相同，则判断删除左指针对应的字符后字符串是否是回文字符串，或者判断删除右指针对应的字符后字符串是否是回文字符串。如果两个指针指向的字符相同，则将左右指针都往中间移动一位，直到两个指针相遇为止。

如果遍历结束，都没有遇到指针指向的字符不相同的情况，那么字符串本身就是一个回文字符串，返回 true 即可。

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

func validPalindrome(s string) bool {
	check := func(i, j int) bool {
		for ; i < j; i, j = i+1, j-1 {
			if s[i] != s[j] {
				return false
			}
		}
		return true
	}
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return check(i+1, j) || check(i, j-1)
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

738. 单调递增的数字

中等1 种解法

标签：贪心、数学

题目、示例与约束

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

0 <= n <= 10⁹

方法一：贪心 · Go 实现

思考

求不超过 $n$ 的最大各位非降数。从 $n$ 向下逐个检查位数过多；需要直接改数字本身。

从高位找到第一处下降后，若只把后面改成 $9$ ，前面可能仍大于原数。应把下降处左侧连续偏大的位都减一，直到重新非降，再把右侧全部置 $9$ ，得到的是不超过 $n$ 的最大非降数。

先扫到第一处 $s [i - 1] > s [i]$ ，再回退减一，最后把 $i$ 之后写成 $9$ 。位数为 $O (\log n)$ 。

从数字 n 的高位开始，找到第一个不满足 $n_{i - 1} \leq n_{i}$ 的位置 $i$ 。

然后，从后往前，只要发现 $n_{i - 1} > n_{i}$ ，就将 $n_{i - 1}$ 减 1。

最后将位置 $i$ 之后的所有数字都置为 9 即可。

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

func monotoneIncreasingDigits(n int) int {
	s := []byte(strconv.Itoa(n))
	i := 1
	for ; i < len(s) && s[i-1] <= s[i]; i++ {
	}
	if i < len(s) {
		for ; i > 0 && s[i-1] > s[i]; i-- {
			s[i-1]--
		}
		i++
		for ; i < len(s); i++ {
			s[i] = '9'
		}
	}
	ans, _ := strconv.Atoi(string(s))
	return ans
}

力扣原题 · Doocs 题解来源

757. 设置交集大小至少为2

困难1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个二维整数数组 intervals ，其中 intervals[i] = [start_i, end_i] 表示从 start_i 到 end_i 的所有整数，包括 start_i 和 end_i 。

包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都至少有两个整数在 nums 中。

例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。

返回包含集合可能的最小大小。

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。

示例 2：

输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。

示例 3：

输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。

提示：

1 <= intervals.length <= 3000
intervals[i].length == 2
0 <= start_i < end_i <= 10⁸

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

思考

选尽量少的点，使每个区间至少盖住两个。区间 $3000$ 个，枚举子集不可行。应让点尽量靠右，以便被后续区间复用。

按右端升序、同右端按左端降序排序后，先处理更「紧」的区间。维护已放置的最后两点 $s < e$ 。

区间已含两点则跳过；只含 $e$ 则在右端补 $b$ ；两点都不含则放 $b - 1$ 与 $b$ 。这样每步补点最少且最靠右。

我们希望在数轴上选出尽可能少的整数点，使得每个区间都至少包含两个点。一个经典而有效的策略是按照区间的右端点进行排序，并尽量让已选取的点位于区间的右侧，以便这些点能覆盖更多后续区间。

首先将所有区间按照如下规则排序：

按右端点从小到大；
若右端点相同，按左端点从大到小。

这样排序的原因是：右端点越小的区间“可操作空间”越少，应优先满足；当右端点相同时，左端点更大的区间更窄，更应优先被处理。

随后，我们使用两个变量 $s$ 和 $e$ 分别记录当前所有已处理区间所共同拥有的 倒数第二个点 和 最后一个点。初始时 $s = e = - 1$ ，表示还没有放置任何点。

接下来依次处理排序后的区间 $[a, b]$ ，根据它与 ${s, e}$ 的关系分三种情况讨论：

若 $a \leq s$ ：当前区间已包含 $s$ 和 $e$ 两个点，无需额外放点。
若 $s < a \leq e$ ：当前区间只包含一个点（即 $e$ ），还需要补一个点。为了让新点对后续区间最有帮助，我们选择在区间最右侧的点 $b$ 。此时更新 $ans = ans + 1$ ，并将新的两点设为 ${e, b}$ 。
若 $a > e$ ：当前区间完全不包含已有的两个点，需要补两个点。最优选择是在区间最右侧放置 ${b - 1, b}$ 。此时更新 $ans = ans + 2$ ，并将新的两点设为 ${b - 1, b}$ 。

最终返回总共放置的点数 $ans$ 。

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

func intersectionSizeTwo(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		a, b := intervals[i], intervals[j]
		if a[1] == b[1] {
			return a[0] > b[0]
		}
		return a[1] < b[1]
	})
	ans := 0
	s, e := -1, -1
	for _, v := range intervals {
		a, b := v[0], v[1]
		if a <= s {
			continue
		}
		if a > e {
			ans += 2
			s, e = b-1, b
		} else {
			ans += 1
			s, e = e, b
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

763. 划分字母区间

中等1 种解法

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

题目、示例与约束

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

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

方法一：贪心 · Go 实现

思考

要把串切成尽量多的段，使每段字母不在其他段出现。长度 $500$ ，关键是每个字母的最后出现位置决定它必须被圈进哪一段。

从左扫描并维护当前段必须覆盖到的最右下标：每见到一个字母就用它的末次位置扩大右端。走到该右端才能安全切开。

先建 $last$ ，再一遍贪心切段，记下长度。时间 $O (n)$ 。

我们先用数组或哈希表 $last$ 记录字符串 $s$ 中每个字母最后一次出现的位置。

接下来我们使用贪心的方法，将字符串划分为尽可能多的片段。

从左到右遍历字符串 $s$ ，遍历的同时维护当前片段的开始下标 $j$ 和结束下标 $i$ ，初始均为 $0$ 。

对于每个访问到的字母 $c$ ，获取到最后一次出现的位置 $last [c]$ 。由于当前片段的结束下标一定不会小于 $last [c]$ ，因此令 $mx = max (mx, last [c])$ 。

当访问到下标 $mx$ 时，意味着当前片段访问结束，当前片段的下标范围是 $[j, . . i]$ ，长度为 $i - j + 1$ ，我们将其添加到结果数组中。然后令 $j = i + 1$ , 继续寻找下一个片段。

重复上述过程，直至字符串遍历结束，即可得到所有片段的长度。

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

func partitionLabels(s string) (ans []int) {
	last := [26]int{}
	for i, c := range s {
		last[c-'a'] = i
	}
	var mx, j int
	for i, c := range s {
		mx = max(mx, last[c-'a'])
		if mx == i {
			ans = append(ans, i-j+1)
			j = i + 1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

767. 重构字符串

中等2 种解法

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

题目、示例与约束

给定一个字符串 s ，检查是否能重新排布其中的字母，使得任意两个相邻字符不相同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例 1:

输入: s = "aab"
输出: "aba"

示例 2:

输入: s = "aaab"
输出: ""

提示:

1 <= s.length <= 500
s 只包含小写字母

方法一：哈希表 · Go 实现

思考

重排使相邻字符不同。若某字符超过 $⌈ n / 2 ⌉$ 次则不可能。长度有限，先判断再隔位填充。

出现最多的字符先放在偶数下标，放满后从下标 $1$ 继续。这样最高频字符被尽量隔开。

按频次从大到小写入答案数组，越界则改到奇数位。

利用哈希表 cnt 统计字符串 s 中每个字符出现的次数。

若最大的出现次数 mx 大于 (n + 1) / 2，说明一定会存在两个相同字符相邻，直接返回 ''。

否则，按字符出现频率从大到小遍历，依次间隔 1 个位置填充字符。若位置大于等于 n，则重置为 1 继续填充。

func reorganizeString(s string) string {
	cnt := make([]int, 26)
	for _, c := range s {
		t := c - 'a'
		cnt[t]++
	}
	mx := slices.Max(cnt)
	n := len(s)
	if mx > (n+1)/2 {
		return ""
	}
	m := [][]int{}
	for i, v := range cnt {
		if v > 0 {
			m = append(m, []int{v, i})
		}
	}
	sort.Slice(m, func(i, j int) bool {
		return m[i][0] > m[j][0]
	})
	ans := make([]byte, n)
	k := 0
	for _, e := range m {
		v, i := e[0], e[1]
		for v > 0 {
			ans[k] = byte('a' + i)
			k += 2
			if k >= n {
				k = 1
			}
			v--
		}
	}
	return string(ans)
}

方法二：贪心 + 哈希表 + 优先队列（大根堆） · Go 实现

思考

隔位填充依赖「最多隔一个」这一特解。写成与「间隔 $k$ 」相同的堆+冷却队列，可复用到 $k = 2$ 。

每次取当前剩余最多的字符，用过后进入长度为 $k$ 的队列，出队后再回堆。拼不出全长则失败。

先用哈希表 cnt 统计每个字母出现的次数，然后构建一个大根堆 pq，其中每个元素是一个 (v, c) 的元组，其中 c 是字母，v 是字母出现的次数。

重排字符串时，我们每次从堆顶弹出一个元素 (v, c)，将 c 添加到结果字符串中，并将 (v-1, c) 放入队列 q 中。当队列 q 的长度达到 $k$ （本题中 $k$ 为 2）及以上时，弹出队首元素，若此时 v 大于 0，则将队首元素放入堆中。循环，直至堆为空。

最后判断结果字符串的长度，若与 s 长度相等，则返回结果字符串，否则返回空串。

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

相似题目：

func reorganizeString(s string) string {
	return rearrangeString(s, 2)
}

func rearrangeString(s string, k int) string {
	cnt := map[byte]int{}
	for i := range s {
		cnt[s[i]]++
	}
	pq := hp{}
	for c, v := range cnt {
		heap.Push(&pq, pair{v, c})
	}
	ans := []byte{}
	q := []pair{}
	for len(pq) > 0 {
		p := heap.Pop(&pq).(pair)
		v, c := p.v, p.c
		ans = append(ans, c)
		q = append(q, pair{v - 1, c})
		if len(q) >= k {
			p = q[0]
			q = q[1:]
			if p.v > 0 {
				heap.Push(&pq, p)
			}
		}
	}
	if len(ans) == len(s) {
		return string(ans)
	}
	return ""
}

type pair struct {
	v int
	c byte
}

type hp []pair

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

力扣原题 · Doocs 题解来源

768. 最多能完成排序的块 II

困难1 种解法

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

题目、示例与约束

给你一个整数数组 arr 。

将 arr 分割成若干块，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

返回能将数组分成的最多块数？

示例 1：

输入：arr = [5,4,3,2,1]
输出：1
解释：
将数组分成2块或者更多块，都无法得到所需的结果。 
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

示例 2：

输入：arr = [2,1,3,4,4]
输出：4
解释：
可以把它分成两块，例如 [2, 1], [3, 4, 4]。 
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

提示：

1 <= arr.length <= 2000
0 <= arr[i] <= 10⁸

方法一：单调栈 · Go 实现

思考

数组可有重复，求最多切成多少块，使各块分别排序后整体有序。 $n \leq 2000$ ，枚举切点需快速判断「左侧都 $\leq$ 右侧」。

从左到右，已形成的块的最大值应单调不降。新值若小于栈顶，说明它必须并入前面某几块，弹出直到栈顶不大于它，再把原先的块最大值压回。

栈里留下的每个最大值对应一块，栈长即答案。

根据题目，我们可以发现，从左到右，每个分块都有一个最大值，并且这些分块的最大值呈单调递增（非严格递增）。我们可以用一个栈来存储这些分块的最大值。最后得到的栈的大小，也就是题目所求的最多能完成排序的块。

时间复杂度 $O (n)$ ，其中 $n$ 表示 $arr$ 的长度。

func maxChunksToSorted(arr []int) int {
	var stk []int
	for _, v := range arr {
		if len(stk) == 0 || stk[len(stk)-1] <= v {
			stk = append(stk, v)
		} else {
			mx := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			for len(stk) > 0 && stk[len(stk)-1] > v {
				stk = stk[:len(stk)-1]
			}
			stk = append(stk, mx)
		}
	}
	return len(stk)
}

力扣原题 · Doocs 题解来源

769. 最多能完成排序的块

中等2 种解法

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

题目、示例与约束

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。

示例 2:

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

提示:

n == arr.length
1 <= n <= 10
0 <= arr[i] < n
arr 中每个元素都不同

方法一：贪心 + 一次遍历 · Go 实现

思考

数组是 $0. . n - 1$ 的排列，切块分别排序后应还原。能在 $i$ 切开，当且仅当前 $i + 1$ 个数恰好是 $0. . i$ 。

这等价于前缀最大值等于 $i$ 。一遍维护 $mx$ ，相等则多一块。

由于 $arr$ 是 $[0, . ., n - 1]$ 的一个排列，若已遍历过的数中的最大值 $mx$ 与当前遍历到的下标 $i$ 相等，说明可以进行一次分割，累加答案。

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

func maxChunksToSorted(arr []int) int {
	ans, mx := 0, 0
	for i, v := range arr {
		mx = max(mx, v)
		if i == mx {
			ans++
		}
	}
	return ans
}

方法二：单调栈 · Go 实现

思考

方法一用到了「值等于下标」这一排列性质，有重复时失效。块最大值单调栈与 768 相同，不依赖值域。

新值小于栈顶则合并前面的块，最后栈长为块数。

方法一的解法有一定的局限性，若数组中存在重复元素，就无法得到正确的答案。

根据题目，我们可以发现，从左到右，每个分块都有一个最大值，并且这些分块的最大值呈单调递增。我们可以用一个栈来存储这些分块的最大值。最后得到的栈的大小，也就是题目所求的最多能完成排序的块。

以上这种解法，不仅可以解决本题，也可以解决 768. 最多能完成排序的块 II 这道困难题。大家可以自行尝试。

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

func maxChunksToSorted(arr []int) int {
	stk := []int{}
	for _, v := range arr {
		if len(stk) == 0 || v >= stk[len(stk)-1] {
			stk = append(stk, v)
		} else {
			mx := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			for len(stk) > 0 && stk[len(stk)-1] > v {
				stk = stk[:len(stk)-1]
			}
			stk = append(stk, mx)
		}
	}
	return len(stk)
}

力扣原题 · Doocs 题解来源

781. 森林中的兔子

中等1 种解法

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

题目、示例与约束

森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只其它兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。 
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。

示例 2：

输入：answers = [10,10,10]
输出：11

提示：

1 <= answers.length <= 1000
0 <= answers[i] < 1000

方法一：贪心 + 哈希表 · Go 实现

思考

回答 $x$ 表示该颜色共有 $x + 1$ 只。不同回答不能同色；相同回答可以分到若干组，每组最多 $x + 1$ 只。

要人数最少，同答 $x$ 的 $v$ 只兔子应尽量填满大小为 $x + 1$ 的组，组数为 $⌈ v / (x + 1) ⌉$ 。

计数后对每种 $x$ 累加组数乘组大小。

根据题目描述，回答相同的兔子，可能属于同一种颜色，而回答不同的兔子，不可能属于同一种颜色。

因此，我们用一个哈希表 $cnt$ 记录每种回答出现的次数。对于每种回答 $x$ 及其出现次数 $v$ ，我们按照每种颜色有 $x + 1$ 只兔子的原则，计算出兔子的最少数量，并将其加入答案。

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

func numRabbits(answers []int) (ans int) {
	cnt := map[int]int{}
	for _, x := range answers {
		cnt[x]++
	}
	for x, v := range cnt {
		group := x + 1
		ans += (v + group - 1) / group * group
	}
	return
}

力扣原题 · Doocs 题解来源

807. 保持城市天际线

中等1 种解法

标签：贪心、数组、矩阵

题目、示例与约束

给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的高度。

城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。

我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。

在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。

示例 1：

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

示例 2：

输入：grid = [[0,0,0],[0,0,0],[0,0,0]]
输出：0
解释：增加任何建筑物的高度都会导致天际线的变化。

提示：

n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100

方法一：贪心 · Go 实现

思考

天际线由每行、每列的最大值决定，升高某格不能超过其所在行、列的天际线。 $n \leq 50$ ，先扫出各行列最大值再逐格计算即可。

格子 $(i, j)$ 最多升到 $min (rowMax [i], colMax [j])$ ，与原高度之差即为该格贡献。对所有格子求和得到总增高。

根据题目描述，我们可以将每个单元格 $(i, j)$ 的值增加至第 $i$ 行的最大值和第 $j$ 列的最大值中的较小值，这样可以保证不影响天际线，即每个单元格增加的高度为 $min (rowMax [i], colMax [j]) - grid [i] [j]$ 。

因此，我们可以先遍历一次矩阵，分别计算出每行和每列的最大值，记录在数组 $rowMax$ 和 $colMax$ 中，然后再遍历一次矩阵，计算出答案即可。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n)$ 。其中 $n$ 为矩阵 $grid$ 的边长。

func maxIncreaseKeepingSkyline(grid [][]int) (ans int) {
	rowMax := make([]int, len(grid))
	colMax := make([]int, len(grid[0]))
	for i, row := range grid {
		for j, x := range row {
			rowMax[i] = max(rowMax[i], x)
			colMax[j] = max(colMax[j], x)
		}
	}
	for i, row := range grid {
		for j, x := range row {
			ans += min(rowMax[i], colMax[j]) - x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

826. 安排工作以达到最大收益

中等2 种解法

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

题目、示例与约束

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人最多只能安排一个工作，但是一个工作可以 完成多次 。

举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

示例 1：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

提示:

n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 10⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵

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

思考

每个工人只能做难度不超过其能力的工作，并取其中利润最大者。 $n, m \leq 10^{4}$ ，对每个工人扫描全部工作偏慢。

将工人与工作分别按能力、难度排序后双指针推进：能力单调不减，可维护当前可达的最大利润。每个工人 $O (1)$ 取该最大值。

我们可以将工作按照能力升序排列，然后将工作按照难度升序排列。

然后我们遍历工人，对于每个工人，我们找出他能完成的工作中收益最大的那个，然后将这个收益加到答案中。

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

func maxProfitAssignment(difficulty []int, profit []int, worker []int) (ans int) {
	sort.Ints(worker)
	n := len(profit)
	jobs := make([][2]int, n)
	for i, p := range profit {
		jobs[i] = [2]int{difficulty[i], p}
	}
	sort.Slice(jobs, func(i, j int) bool { return jobs[i][0] < jobs[j][0] })
	mx, i := 0, 0
	for _, w := range worker {
		for ; i < n && jobs[i][0] <= w; i++ {
			mx = max(mx, jobs[i][1])
		}
		ans += mx
	}
	return
}

方法二：动态规划 · Go 实现

思考

双指针需要排序。难度上限为 $10^{5}$ ，也可用数组 $f [d]$ 记录难度恰为 $d$ 的最大利润，再前缀取最大值，得到「能力不超过 $i$ 时的最佳利润」。

每个工人直接查表，省去对工人排序，适合难度范围不大的情形。

我们不妨记 $m = max (difficulty)$ ，定义一个长度为 $m + 1$ 的数组 $f$ ，其中 $f [i]$ 表示难度小于等于 $i$ 的工作中收益的最大值，初始时 $f [i] = 0$ 。

然后我们遍历工作，对于每个工作 $(d, p)$ ，我们更新 $f [d] = max (f [d], p)$ 。

接下来，我们从 $1$ 到 $m$ 遍历，对于每个 $i$ ，我们更新 $f [i] = max (f [i], f [i - 1])$ 。

最后，我们遍历工人，对于每个工人 $w$ ，我们将 $f [min (w, m)]$ 加到答案中。

时间复杂度 $O (n + M)$ ，空间复杂度 $O (M)$ 。其中 $n$ 是数组 profit 的长度，而 $M$ 是数组 difficulty 中的最大值。

func maxProfitAssignment(difficulty []int, profit []int, worker []int) (ans int) {
	m := slices.Max(difficulty)
	f := make([]int, m+1)
	for i, d := range difficulty {
		f[d] = max(f[d], profit[i])
	}
	for i := 1; i <= m; i++ {
		f[i] = max(f[i], f[i-1])
	}
	for _, w := range worker {
		ans += f[min(w, m)]
	}
	return
}

力扣原题 · Doocs 题解来源

846. 一手顺子

中等2 种解法

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

题目、示例与约束

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

示例 1：

输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出：true
解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例 2：

输入：hand = [1,2,3,4,5], groupSize = 4
输出：false
解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

提示：

1 <= hand.length <= 10⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

注意：此题目与 1296 重复：https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/

方法一：哈希表 + 排序 · Go 实现

思考

把手牌分成若干长度为 $groupSize$ 的连续组。张数不能整除则失败。 $n \leq 10^{4}$ ，应从最小牌开始贪心取组。

计数后按牌面排序，每张仍剩余的牌作为一组起点，连续 $groupSize$ 张各减一，缺牌则失败。

我们首先判断数组 $hand$ 的长度是否能被 $groupSize$ 整除，如果不能整除，说明无法将数组划分成若干个长度为 $groupSize$ 的子数组，直接返回 $false$ 。

接下来，我们用一个哈希表 $cnt$ 统计数组 $hand$ 中每个数字出现的次数，然后对数组 $hand$ 进行排序。

然后，我们遍历排序后的数组 $hand$ ，对于每个数字 $x$ ，如果 $cnt [x]$ 不为 $0$ ，我们枚举 $x$ 到 $x + groupSize - 1$ 的每个数字 $y$ ，如果 $cnt [y]$ 为 $0$ ，说明无法将数组划分成若干个长度为 $groupSize$ 的子数组，直接返回 $false$ 。否则，我们将 $cnt [y]$ 减 $1$ 。

遍历结束后，说明可以将数组划分成若干个长度为 $groupSize$ 的子数组，返回 $true$ 。

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

func isNStraightHand(hand []int, groupSize int) bool {
	if len(hand)%groupSize != 0 {
		return false
	}
	sort.Ints(hand)
	cnt := map[int]int{}
	for _, x := range hand {
		cnt[x]++
	}
	for _, x := range hand {
		if cnt[x] > 0 {
			for y := x; y < x+groupSize; y++ {
				if cnt[y] == 0 {
					return false
				}
				cnt[y]--
			}
		}
	}
	return true
}

方法二：有序集合 · Go 实现

思考

排序整副手牌会扫到计数已为 $0$ 的牌。用有序映射直接取当前最小键作为下一组起点，缺键或减完后删除即可。

逻辑与方法一相同，只是用有序集合保证每次取出的都是剩余牌中的最小值。

与方法一类似，我们首先判断数组 $hand$ 的长度是否能被 $groupSize$ 整除，如果不能整除，说明无法将数组划分成若干个长度为 $groupSize$ 的子数组，直接返回 $false$ 。

接下来，我们用一个有序集合 $sd$ 统计数组 $hand$ 中每个数字出现的次数。

然后，我们循环取出有序集合中的最小值 $x$ ，然后枚举 $x$ 到 $x + groupSize - 1$ 的每个数字 $y$ ，如果这些数字在有序集合中出现的次数都不为 $0$ ，则我们将这些数字的出现次数减 $1$ ，如果出现次数减 $1$ 后为 $0$ ，则将该数字从有序集合中删除，否则说明无法将数组划分成若干个长度为 $groupSize$ 的子数组，返回 $false$ 。如果可以将数组划分成若干个长度为 $groupSize$ 的子数组，则遍历结束后返回 $true$ 。

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

func isNStraightHand(hand []int, groupSize int) bool {
	if len(hand)%groupSize != 0 {
		return false
	}
	tm := treemap.NewWithIntComparator()
	for _, x := range hand {
		if v, ok := tm.Get(x); ok {
			tm.Put(x, v.(int)+1)
		} else {
			tm.Put(x, 1)
		}
	}
	for !tm.Empty() {
		x, _ := tm.Min()
		for y := x.(int); y < x.(int)+groupSize; y++ {
			if v, ok := tm.Get(y); ok {
				if v.(int) == 1 {
					tm.Remove(y)
				} else {
					tm.Put(y, v.(int)-1)
				}
			} else {
				return false
			}
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

857. 雇佣 K 名工人的最低成本

困难1 种解法

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

题目、示例与约束

有 n 名工人。给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个 工资组。在雇佣一组 k 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。与实际答案误差相差在 10^-5 以内的答案将被接受。

示例 1：

输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。

示例 2：

输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

提示：

n == quality.length == wage.length
1 <= k <= n <= 10⁴
1 <= quality[i], wage[i] <= 10⁴

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

思考

工资须按同一比率发放且每人不少于期望，选 $k$ 人使总工资最小。比率由团中 $wage / quality$ 的最大值决定。 $n \leq 10^{4}$ ，枚举子集不可行。

按比率升序加入工人，当前比率已能覆盖团内所有人；用大根堆丢掉质量最大者，保持团大小为 $k$ 。每次恰好 $k$ 人时用「当前比率 $\times$ 质量之和」更新答案。

我们假设选取了某一个工资组，总工作质量为 tot，总支付金额为 c。每个工人的工作质量为 $q_{i}$ ，工资为 $w_{i}$ 。那么，对于此工资组的每个工人，均满足 $c \times \frac{q_{i}}{t o t} \geq w_{i}$ 。即 $c \geq t o t \times \frac{w_{i}}{q_{i}}$ 。

在总工作质量 tot 固定的情况下，支付的金额取决于权重 $\frac{w_{i}}{q_{i}}$ 的最大值。

我们可以从小到大枚举权重 $\frac{w_{i}}{q_{i}}$ 作为工资组的最大值，此时工资组其他人员只需要在权重小于等于这个值的集合中，选取工作质量最小的 $k - 1$ 名工人来组成工资组即可。因此，可以用优先队列（最大堆）维护工作质量最小的 $k - 1$ 名工人。

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

相似题目：

1383. 最大的团队表现值

func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
	t := []pair{}
	for i, q := range quality {
		t = append(t, pair{float64(wage[i]) / float64(q), q})
	}
	sort.Slice(t, func(i, j int) bool { return t[i].x < t[j].x })
	tot := 0
	var ans float64 = 1e18
	pq := hp{}
	for _, e := range t {
		tot += e.q
		heap.Push(&pq, e.q)
		if pq.Len() == k {
			ans = min(ans, float64(tot)*e.x)
			tot -= heap.Pop(&pq).(int)
		}
	}
	return ans
}

type pair struct {
	x float64
	q int
}

type hp struct{ sort.IntSlice }

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

力扣原题 · Doocs 题解来源

860. 柠檬水找零

简单1 种解法

标签：贪心、数组

题目、示例与约束

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

1 <= bills.length <= 10⁵
bills[i] 不是 5 就是 10 或是 20

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

思考

只有 $5$ 、 $10$ 、 $20$ ，找零必须用手头已有的钞票。 $n \leq 10^{5}$ ，应贪心：收 $20$ 时优先配一张 $10$ 加一张 $5$ ，否则三张 $5$ 。

维护 $5$ 与 $10$ 的张数，任一步 $5$ 变为负数即失败。无需保存整段交易历史。

我们从前往后遍历账单数组 $b i l l s$ ，对于当前遍历到的账单：

如果是 $5$ 美元，那么直接收下即可；
如果是 $10$ 美元，那么需要找零 $5$ 美元；
如果是 $20$ 美元，那么需要找零 $15$ 美元，此时有两种找零方式：找零 $1$ 张 $10$ 美元 + $1$ 张 $5$ 美元；找零 $3$ 张 $5$ 美元。我们优先用第一种找零方式，如果没有足够的 $10$ 美元，那么用第二种方式；
如果发现 $5$ 美元的数量不够，直接返回 false。

遍历结束，说明我们没有遇到无法找零的情况，返回 true 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为账单数组 $b i l l s$ 的长度。

func lemonadeChange(bills []int) bool {
	five, ten := 0, 0
	for _, v := range bills {
		if v == 5 {
			five++
		} else if v == 10 {
			ten++
			five--
		} else {
			if ten > 0 {
				ten--
				five--
			} else {
				five -= 3
			}
		}
		if five < 0 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

861. 翻转矩阵后的得分

中等1 种解法

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

题目、示例与约束

给你一个大小为 m x n 的二元矩阵 grid ，矩阵中每个元素的值为 0 或 1 。

一次移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

在执行任意次移动后（含 0 次），返回可能的最高分数。

示例 1：

输入：grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

示例 2：

输入：grid = [[0]]
输出：1

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid[i][j] 为 0 或 1

方法一：贪心 · Go 实现

思考

行列翻转任意次，最大化按二进制解读的矩阵得分。 $m, n \leq 20$ ，穷举行翻转可行但无必要：最高位必须尽量为 $1$ ，否则该行贡献减半。

先翻转使每行首列为 $1$ 。此后每列只比较 $1$ 的个数与 $0$ 的个数，取较多的一侧乘上该列权值。列翻转互不影响。

我们注意到，对于任意一个翻转方案，翻转的次序不影响最后的结果。因此我们可以先考虑所有的行翻转，再考虑所有的列翻转。

每一行的数字要尽可能大，因此，我们遍历每一行，若行首元素为 $0$ ，则将该行进行翻转。

接下来，对于每一列 $j$ ，我们统计该列中 $0$ 和 $1$ 的数量，令 $c n t$ 为其中的最大值，则该列的贡献为 $c n t \times 2^{n - j - 1}$ 。对所有列的贡献进行累加，即可得到答案。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (1)$ 。其中 $m$ , $n$ 分别为矩阵的行数和列数。

func matrixScore(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	for i := 0; i < m; i++ {
		if grid[i][0] == 0 {
			for j := 0; j < n; j++ {
				grid[i][j] ^= 1
			}
		}
	}
	ans := 0
	for j := 0; j < n; j++ {
		cnt := 0
		for i := 0; i < m; i++ {
			cnt += grid[i][j]
		}
		if cnt < m-cnt {
			cnt = m - cnt
		}
		ans += cnt * (1 << (n - j - 1))
	}
	return ans
}

力扣原题 · Doocs 题解来源

870. 优势洗牌

中等1 种解法

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

题目、示例与约束

给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示：

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

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

思考

重排 $n u m s 1$ 使严格大于 $n u m s 2$ 对应位的个数最多。田忌赛马： $n \leq 10^{5}$ ，应对 $n u m s 2$ 从大到小，能赢就用最小能赢的，否则用全局最小去填。

将 $n u m s 1$ 排序、 $n u m s 2$ 按下标排序后双指针：当前最小值打得过则打最弱对手，否则送给当前最强对手。

类似田忌赛马。将 $n u m s 1$ , $n u m s 2$ 按照升序排列。然后遍历 $n u m s 1$ 中的每个元素 $v$ ，若在 $n u m s 2 [i . . j]$ 中找不到比 $v$ 小的，则将 $v$ 与当前 $n u m s 2 [i . . j]$ 中的最大元素匹配。

时间复杂度 $O (n l o g n)$ 。

func advantageCount(nums1 []int, nums2 []int) []int {
	n := len(nums1)
	t := make([][]int, n)
	for i, v := range nums2 {
		t[i] = []int{v, i}
	}
	sort.Slice(t, func(i, j int) bool {
		return t[i][0] < t[j][0]
	})
	sort.Ints(nums1)
	ans := make([]int, n)
	i, j := 0, n-1
	for _, v := range nums1 {
		if v <= t[i][0] {
			ans[t[j][1]] = v
			j--
		} else {
			ans[t[i][1]] = v
			i++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

881. 救生艇

中等1 种解法

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

题目、示例与约束

给定数组 people 。people[i]表示第 i个人的体重，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

提示：

1 <= people.length <= 5 * 10⁴
1 <= people[i] <= limit <= 3 * 10⁴

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

思考

每艘船最多两人且体重和不超过 $limit$ ，求最少船数。 $n \leq 5 \cdot 10^{4}$ ，应让最重者尽量与最轻者同船。

排序后双指针：两端能同船则两人一起走，否则最重者独自走。每步消耗一艘船，直到指针交错。

排序后，使用双指针分别指向数组首尾，每次取两个指针指向的元素之和与 limit 比较，如果小于等于 limit，则两个指针同时向中间移动一位，否则只移动右指针。累加答案即可。

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

func numRescueBoats(people []int, limit int) int {
	sort.Ints(people)
	ans := 0
	for i, j := 0, len(people)-1; i <= j; j-- {
		if people[i]+people[j] <= limit {
			i++
		}
		ans++
	}
	return ans
}

力扣原题 · Doocs 题解来源

910. 最小差值 II

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的分数是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小分数。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：

输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

提示：

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

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

思考

每个数只能 $+ k$ 或 $- k$ ，枚举 $2^{n}$ 种分配不可行。排序后，较小的应倾向 $+ k$ ，较大的倾向 $- k$ ，最优划分是某个前缀加 $k$ 、后缀减 $k$ 。

枚举分界 $i$ ，新的最小值为 $min (n u m s [0] + k, n u m s [i] - k)$ ，最大值为 $max (n u m s [i - 1] + k, n u m s [- 1] - k)$ ，取所有极差与原极差的最小值。

根据题目要求，我们需要求数组中的元素最大值与最小值差值的最小值。每个元素可以加上或者减去 $k$ ，因此我们可以将数组中的元素分为两部分，一部分加上 $k$ ，一部分减去 $k$ 。那么，我们应该将数组中的较大值减去 $k$ ，较小值加上 $k$ ，这样才能保证最大值与最小值的差值最小。

因此，我们可以先将数组排序，然后枚举数组中的每个元素，将其分为两部分，一部分加上 $k$ ，一部分减去 $k$ ，并计算最大值与最小值的差值。最后，取所有差值中的最小值即可。

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

func smallestRangeII(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	ans := nums[n-1] - nums[0]
	for i := 1; i < n; i++ {
		mi := min(nums[0]+k, nums[i]-k)
		mx := max(nums[i-1]+k, nums[n-1]-k)
		ans = min(ans, mx-mi)
	}
	return ans
}

力扣原题 · Doocs 题解来源

921. 使括号有效的最少添加

中等2 种解法

标签：栈、贪心、字符串、括号序列

题目、示例与约束

只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号

例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

示例 1：

输入：s = "())"
输出：1

示例 2：

输入：s = "((("
输出：3

提示：

1 <= s.length <= 1000
s 只包含 '(' 和 ')' 字符。

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

思考

添加最少括号使序列合法。栈匹配后剩余的左右括号都必须各补一个配对。左括号入栈，右括号优先与栈顶左括号抵消，否则入栈；结束时栈长即为答案。

这个问题属于经典的括号匹配问题，可以使用“贪心 + 栈”来解决。

遍历字符串 $s$ 的每个字符 $c$ ：

若 $c$ 为左括号，直接将 $c$ 入栈；
若 $c$ 为右括号，此时如果栈不为空，且栈顶元素为左括号，则将栈顶元素出栈，表示匹配成功；否则将 $c$ 入栈。

遍历结束后，栈中剩余的元素个数即为需要添加的括号数。

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

func minAddToMakeValid(s string) int {
	stk := []rune{}
	for _, c := range s {
		if c == ')' && len(stk) > 0 && stk[len(stk)-1] == '(' {
			stk = stk[:len(stk)-1]
		} else {
			stk = append(stk, c)
		}
	}
	return len(stk)
}

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

思考

栈中实际只需记录未匹配的左括号个数，不必存字符。用 $c n t$ 计待匹配左括号，无法匹配的右括号计入 $a n s$ ，最后再把剩余 $c n t$ 加上，空间降为常数。

方法一借助了栈来实现括号匹配，也可以直接通过计数来实现。

定义变量 cnt 表示当前待匹配的左括号个数，变量 ans 记录答案。初始时两个变量的值均为 $0$ 。

同样遍历字符串 $s$ 的每个字符 $c$ ：

若 $c$ 为左括号，将 cnt 的值增加 $1$ ；
若 $c$ 为右括号，此时如果 $c n t > 0$ ，说明当前有左括号可以匹配，将 cnt 的值减 $1$ ；否则说明当前右括号无法匹配，将 ans 的值增加 $1$ 。

遍历结束后，将 cnt 的值加到 ans 中，即为答案。

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

func minAddToMakeValid(s string) int {
	ans, cnt := 0, 0
	for _, c := range s {
		if c == '(' {
			cnt++
		} else if cnt > 0 {
			cnt--
		} else {
			ans++
		}
	}
	ans += cnt
	return ans
}

力扣原题 · Doocs 题解来源

936. 戳印序列

困难1 种解法

标签：栈、贪心、队列、字符串

题目、示例与约束

你想要用小写字母组成一个目标字符串 target。

开始的时候，序列由 target.length 个 '?' 记号组成。而你有一个小写字母印章 stamp。

在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。

举个例子，如果初始序列为 "?????"，而你的印章 stamp 是 "abc"，那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"。（请注意，印章必须完全包含在序列的边界内才能盖下去。）

如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。

例如，如果序列是 "ababc"，印章是 "abc"，那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2]；

另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。

示例 1：

输入：stamp = "abc", target = "ababc"
输出：[0,2]
（[1,0,2] 以及其他一些可能的结果也将作为答案被接受）

示例 2：

输入：stamp = "abca", target = "aabcaca"
输出：[3,0,1]

提示：

1 <= stamp.length <= target.length <= 1000
stamp 和 target 只包含小写字母。

方法一：逆向思维 + 拓扑排序 · Go 实现

思考

正向盖章会被后续覆盖，难以判断何时可以盖。反过来从 $t a r g e t$ 抹成问号：一个窗口当且仅当未覆盖位置都与印章一致时可以“揭掉”。

窗口入度为尚未匹配的位置数，位置指向包含它的未匹配窗口。入度为 $0$ 的窗口入队，揭掉后把它覆盖的格子通知邻接窗口。全部格子被覆盖则将操作序列反转即为正向盖章顺序。

如果我们正向地对序列进行操作，那么处理起来会比较麻烦，因为后续的操作会把前面的操作覆盖掉。我们不妨考虑逆向地对序列进行操作，即从目标字符串 $t a r g e t$ 开始，考虑将 $t a r g e t$ 变成 $? ? ? ? ?$ 的过程。

我们不妨记字母印章的长度为 $m$ ，目标字符串的长度为 $n$ 。如果我们拿着字母印章在目标字符串上操作，那么一共有 $n - m + 1$ 个开始位置可以放置字母印章。我们可以枚举这 $n - m + 1$ 个开始位置，利用类似拓扑排序的方法，逆向地进行操作。

首先，我们明确，每个开始位置都对应着一个长度为 $m$ 的窗口。

接下来，我们定义以下数据结构或变量，其中：

入度数组 $i n d e g$ ，其中 $i n d e g [i]$ 表示第 $i$ 个窗口中有多少位置的字符与字母印章中的字符不同，初始时， $i n d e g [i] = m$ 。若 $i n d e g [i] = 0$ ，说明第 $i$ 个窗口中的字符都与字母印章中的字符相同，那么我们就可以在第 $i$ 个窗口中放置字母印章。
邻接表 $g$ ，其中 $g [i]$ 表示目标字符串 $t a r g e t$ 的第 $i$ 个位置上，所有与字母印章存在不同字符的窗口的集合。
队列 $q$ ，用于存储所有入度为 $0$ 的窗口的编号。
数组 $v i s$ ，用于标记目标字符串 $t a r g e t$ 的每个位置是否已经被覆盖。
数组 $a n s$ ，用于存储答案。

接下来，我们进行拓扑排序。在拓扑排序的每一步中，我们取出队首的窗口编号 $i$ ，并将 $i$ 放入答案数组 $a n s$ 中。然后，我们枚举字母印章中的每个位置 $j$ ，如果第 $i$ 个窗口中的第 $j$ 个位置未被覆盖，那么我们就将其覆盖，并将 $i n d e g$ 数组中所有与第 $i$ 个窗口中的第 $j$ 个位置相同的窗口的入度减少 $1$ 。如果某个窗口的入度变为 $0$ ，那么我们就将其放入队列 $q$ 中等待下一次处理。

在拓扑排序结束后，如果目标字符串 $t a r g e t$ 的每个位置都被覆盖，那么答案数组 $a n s$ 中存储的就是我们要求的答案。否则，目标字符串 $t a r g e t$ 无法被覆盖，我们就返回一个空数组。

时间复杂度 $O (n \times (n - m + 1))$ ，空间复杂度 $O (n \times (n - m + 1))$ 。其中 $n$ 和 $m$ 分别是目标字符串 $t a r g e t$ 和字母印章的长度。

func movesToStamp(stamp string, target string) (ans []int) {
	m, n := len(stamp), len(target)
	indeg := make([]int, n-m+1)
	for i := range indeg {
		indeg[i] = m
	}
	g := make([][]int, n)
	q := []int{}
	for i := 0; i < n-m+1; i++ {
		for j := range stamp {
			if target[i+j] == stamp[j] {
				indeg[i]--
				if indeg[i] == 0 {
					q = append(q, i)
				}
			} else {
				g[i+j] = append(g[i+j], i)
			}
		}
	}
	vis := make([]bool, n)
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		ans = append(ans, i)
		for j := range stamp {
			if !vis[i+j] {
				vis[i+j] = true
				for _, k := range g[i+j] {
					indeg[k]--
					if indeg[k] == 0 {
						q = append(q, k)
					}
				}
			}
		}
	}
	for _, v := range vis {
		if !v {
			return []int{}
		}
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return
}

力扣原题 · Doocs 题解来源

942. 增减字符串匹配

简单1 种解法

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

题目、示例与约束

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'

给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

示例 1：

输入：s = "IDID"
输出：[0,4,1,3,2]

示例 2：

输入：s = "III"
输出：[0,1,2,3]

示例 3：

输入：s = "DDI"
输出：[3,2,0,1]

提示：

1 <= s.length <= 10⁵
s 只包含字符 "I" 或 "D"

方法一：贪心 · Go 实现

思考

用 $0. . n$ 各一次构造排列，使 'I'/'D' 对应相邻升降。 $n \leq 10^{5}$ ，不能回溯。遇 'I' 放当前最小剩余，遇 'D' 放当前最大剩余，最后补上剩下的那个数，贪心即可满足所有相邻关系。

我们可以使用两个指针 low 和 high 分别表示当前的最小值和最大值，然后遍历字符串 s，如果当前字符是 I，那么我们就将 low 加入到结果数组中，并且 low 自增 1；如果当前字符是 D，那么我们就将 high 加入到结果数组中，并且 high 自减 1。

最后，我们将 low 加入到结果数组中，返回结果数组即可。

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

func diStringMatch(s string) (ans []int) {
	low, high := 0, len(s)
	for _, c := range s {
		if c == 'I' {
			ans = append(ans, low)
			low++
		} else {
			ans = append(ans, high)
			high--
		}
	}
	ans = append(ans, low)
	return
}

力扣原题 · Doocs 题解来源

945. 使数组唯一的最小增量

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。

生成的测试用例保证答案在 32 位整数范围内。

示例 1：

输入：nums = [1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2：

输入：nums = [3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

提示：

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

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

思考

每次只能把某个数加一，使最终互不相同，求最少次数。排序后应让每个数不小于“当前已占用的下一个空位” $y$ 。令 $y \leftarrow max (y + 1, x)$ ，增量 $y - x$ 累加即为代价。

我们首先对数组 $nums$ 进行排序，用一个变量 $y$ 记录当前的最大值，初始时 $y = - 1$ 。

然后遍历数组 $nums$ ，对于每个元素 $x$ ，我们将 $y$ 更新为 $max (y + 1, x)$ ，并将操作次数 $y - x$ 累加到结果中。

遍历完成后，返回结果即可。

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

func minIncrementForUnique(nums []int) (ans int) {
	sort.Ints(nums)
	y := -1
	for _, x := range nums {
		y = max(y+1, x)
		ans += y - x
	}
	return
}

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

思考

排序需要 $O (n \log n)$ 。值域加上长度后上界为 $m$ ，可用计数：从低到高，多余的 $c n t [i] - 1$ 个 $i$ 全部挪到 $i + 1$ ，线性扫完值域。

根据题目描述，结果数组的最大值 $m = max (nums) + len (nums)$ ，我们可以使用一个计数数组 $cnt$ 来记录每个元素出现的次数。

然后从 $0$ 到 $m - 1$ 遍历，对于每个元素 $i$ ，如果它出现的次数 $cnt [i]$ 大于 $1$ ，那么我们将 $cnt [i] - 1$ 个元素增加到 $i + 1$ ，并将操作次数累加到结果中。

遍历完成后，返回结果即可。

时间复杂度 $O (m)$ ，空间复杂度 $O (m)$ 。其中 $m$ 是数组 $nums$ 的长度加上数组的最大值。

func minIncrementForUnique(nums []int) (ans int) {
	m := slices.Max(nums) + len(nums)
	cnt := make([]int, m)
	for _, x := range nums {
		cnt[x]++
	}
	for i := 0; i < m-1; i++ {
		if diff := cnt[i] - 1; diff > 0 {
			cnt[i+1] += diff
			ans += diff
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

948. 令牌放置

中等1 种解法

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

题目、示例与约束

你的初始能量为 power，初始分数为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。

你的目标是通过有策略地使用这些令牌以 最大化 总分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：

朝上：如果你当前至少有 tokens[i] 点能量，可以使用令牌 i ，失去 tokens[i] 点能量，并得到 1 分。
朝下：如果你当前至少有 1 分，可以使用令牌 i ，获得 tokens[i] 点能量，并失去 1 分。

在使用任意数量的令牌后，返回我们可以得到的最大分数。

示例 1：

输入：tokens = [100], power = 50
输出：0
解释：因为你的初始分数为 0，无法使令牌朝下。你也不能使令牌朝上因为你的能量（50）比 tokens[0] 少（100）。

示例 2：

输入：tokens = [200,100], power = 150
输出：1
解释：使令牌 1 正面朝上，能量变为 50，分数变为 1 。
不必使用令牌 0，因为你无法使用它来提高分数。可得到的最大分数是 1。

示例 3：

输入：tokens = [100,200,300,400], power = 200
输出：2
解释：按下面顺序使用令牌可以得到 2 分：
1. 令牌 0 (100)正面朝上，能量变为 100 ，分数变为 1
2. 令牌 3 (400)正面朝下，能量变为 500 ，分数变为 0
3. 令牌 1 (200)正面朝上，能量变为 300 ，分数变为 1
4. 令牌 2 (300)正面朝上，能量变为 0 ，分数变为 2

可得的最大分数是 2。

提示：

0 <= tokens.length <= 1000
0 <= tokens[i], power < 10⁴

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

思考

小令牌换分、大令牌换能量，求过程中分数最大值。应花最少能量换分、在必要时用分换回最多能量。排序后左指针买最便宜的，能量不够且仍有分时右指针卖掉最贵的，并持续记录分数峰值。

令牌的使用方法有两种，一种是消耗能量得到分数，一种是消耗分数得到能量。显然，我们应该消耗尽可能少的能量来得到尽可能多的分数。

因此，我们可以将令牌按照消耗能量的多少进行排序，然后使用双指针，一个指针从左向右遍历，一个指针从右向左遍历，每次遍历都尽可能地消耗能量得到分数，然后更新最大分数。如果当前能量不足以消耗当前令牌，那么我们就尝试使用分数来消耗当前令牌，如果分数不足以消耗当前令牌，那么我们就停止遍历。

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

func bagOfTokensScore(tokens []int, power int) (ans int) {
	sort.Ints(tokens)
	i, j := 0, len(tokens)-1
	score := 0
	for i <= j {
		if power >= tokens[i] {
			power -= tokens[i]
			i++
			score++
			ans = max(ans, score)
		} else if score > 0 {
			power += tokens[j]
			j--
			score--
		} else {
			break
		}
	}
	return
}

力扣原题 · Doocs 题解来源

954. 二倍数对数组

中等1 种解法

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

题目、示例与约束

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

示例 1：

输入：arr = [3,1,3,6]
输出：false

示例 2：

输入：arr = [2,1,2,6]
输出：false

示例 3：

输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

提示：

0 <= arr.length <= 3 * 10⁴
arr.length 是偶数
-10⁵ <= arr[i] <= 10⁵

方法一：哈希表 + 排序 · Go 实现

思考

把数组重排成每项都是前一项的两倍。 $0$ 只能与 $0$ 配对，奇数个则失败。其余应按绝对值从小到大匹配：较小的 $x$ 必须能在 $2 x$ 上找到足够次数，否则大数可能已被更小的数占用。计数表记录剩余次数。

func canReorderDoubled(arr []int) bool {
	freq := make(map[int]int)
	for _, v := range arr {
		freq[v]++
	}
	if freq[0]%2 != 0 {
		return false
	}
	var keys []int
	for k := range freq {
		keys = append(keys, k)
	}
	sort.Slice(keys, func(i, j int) bool {
		return abs(keys[i]) < abs(keys[j])
	})
	for _, k := range keys {
		if freq[k*2] < freq[k] {
			return false
		}
		freq[k*2] -= freq[k]
	}
	return true
}

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

力扣原题 · Doocs 题解来源

955. 删列造序 II

中等1 种解法

标签：贪心、数组、字符串

题目、示例与约束

给定由 n 个字符串组成的数组 strs，其中每个字符串长度相等。

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 strs 为["bef", "vyz"]。

假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的，然后请你返回 answer.length 的最小可能值。

示例 1：

输入：strs = ["ca","bb","ac"]
输出：1
解释： 
删除第一列后，strs = ["a", "b", "c"]。
现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。
我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。

示例 2：

输入：strs = ["xc","yb","za"]
输出：0
解释：
strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 strs 的行不需要按字典序排列。
也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：
我们必须删掉每一列。

提示：

n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] 由小写英文字母组成

方法一：贪心 · Go 实现

思考

删除最少列使整行从上到下按字典序非降。字典序由左到右第一处不同决定，已分出大小的相邻对不再受后面列影响。从左扫描：若某对尚未确定且当前列逆序，则该列必须删；否则用本列严格升序把对标记为已确定。

字符串按字典序比较时，从左到右比较，第一个不相等的字符决定了两个字符串的大小关系。因此我们可以从左到右遍历每一列，判断当前列是否需要删除。

我们维护一个长度为 $n - 1$ 的布尔数组 $st$ ，表示相邻的字符串对是否已经确定了大小关系。如果已经确定了大小关系，那么后续在这两个字符串之间的任何字符比较都不会改变它们的大小关系。

对于每一列 $j$ ，我们遍历所有相邻的字符串对 $(strs [i], strs [i + 1])$ ：

如果 $st [i]$ 为假且 $strs [i] [j] > strs [i + 1] [j]$ ，说明当前列必须删除，我们将答案加一并跳过该列的处理；
否则，如果 $st [i]$ 为假且 $strs [i] [j] < strs [i + 1] [j]$ ，说明当前列确定了这两个字符串的大小关系，我们将 $st [i]$ 设为真。

遍历完所有列后，答案即为需要删除的列数。

这个贪心策略是最优的，因为字典序由从左到右第一个不同列决定。若当前列不删除且导致某对字符串顺序错误，则无论后续列如何，都无法修正这一错误，因此必须删除当前列。若当前列不删除且不导致任何字符串对顺序错误，则保留当前列不会影响最终的字典序关系。

时间复杂度 $O (n \times m)$ ，空间复杂度 $O (n)$ ，其中 $n$ 和 $m$ 分别为字符串数组的长度和每个字符串的长度。

func minDeletionSize(strs []string) int {
	n := len(strs)
	m := len(strs[0])
	st := make([]bool, n-1)
	ans := 0
	for j := 0; j < m; j++ {
		mustDel := false
		for i := 0; i < n-1; i++ {
			if !st[i] && strs[i][j] > strs[i+1][j] {
				mustDel = true
				break
			}
		}
		if mustDel {
			ans++
		} else {
			for i := 0; i < n-1; i++ {
				if !st[i] && strs[i][j] < strs[i+1][j] {
					st[i] = true
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

969. 煎饼排序

中等1 种解法

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

题目、示例与约束

给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。

一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length
反转子数组 arr[0...k-1]（下标从 0 开始）

例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

示例 1：

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。

示例 2：

输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。

提示：

1 <= arr.length <= 100
1 <= arr[i] <= arr.length
arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列）

方法一 · Go 实现

思考

烙饼排序每次反转前缀。数组是 $1. . n$ 的排列，可从大到小就位：先把 $k$ 翻到最前，再翻到最终位置 $k$ 。记录两次翻转的前缀长度。已就位的后缀不必再动。

func pancakeSort(arr []int) []int {
	var ans []int
	n := len(arr)
	reverse := func(j int) {
		for i := 0; i < j; i, j = i+1, j-1 {
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	for i := n - 1; i > 0; i-- {
		j := i
		for ; j > 0 && arr[j] != i+1; j-- {
		}
		if j < i {
			if j > 0 {
				ans = append(ans, j+1)
				reverse(j)
			}
			ans = append(ans, i+1)
			reverse(i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

976. 三角形的最大周长

简单1 种解法

标签：贪心、数组、数学、多边形、排序、快速排序

题目、示例与约束

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形:1 2 2。

示例 2：

输入：nums = [1,2,1,10]
输出：0
解释：
你不能用边长 1,1,2 来组成三角形。
不能用边长 1,1,10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。

提示：

3 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁶

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

思考

三边 $a \leq b \leq c$ 能围成三角形当且仅当 $a + b > c$ ，周长尽量大。枚举所有三元组为立方级。排序后从大到小枚举 $c$ ，取紧邻的两条边；一旦满足不等式即为最大周长，否则该 $c$ 不可能。

我们不妨假设三角形的三条边长分别为 $a \leq b \leq c$ ，则三角形的面积不为零等价于 $a + b > c$ 。

我们可以枚举最大的边长 $c$ ，然后从剩下的边长中选取两个最大的边长 $a$ 和 $b$ ，如果 $a + b > c$ ，则可以构成一个面积不为零的三角形，且该三角形的周长最大；否则继续枚举下一个最大的边长 $c$ 。

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

func largestPerimeter(nums []int) int {
	sort.Ints(nums)
	for i := len(nums) - 1; i >= 2; i-- {
		if c := nums[i-1] + nums[i-2]; c > nums[i] {
			return c + nums[i]
		}
	}
	return 0
}

力扣原题 · Doocs 题解来源

984. 不含 AAA 或 BBB 的字符串

中等1 种解法

标签：贪心、字符串

题目、示例与约束

给定两个整数 a 和 b ，返回任意字符串 s ，要求满足：

s 的长度为 a + b，且正好包含 a 个 'a' 字母与 b 个 'b' 字母；
子串 'aaa' 没有出现在 s 中；
子串 'bbb' 没有出现在 s 中。

示例 1：

输入：a = 1, b = 2
输出："abb"
解释："abb", "bab" 和 "bba" 都是正确答案。

示例 2：

输入：a = 4, b = 1
输出："aabaa"

提示：

0 <= a, b <= 100
对于给定的 a 和 b，保证存在满足要求的 s

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

思考

用 $a$ 个 'a' 与 $b$ 个 'b' 构造不含 aaa/bbb 的串。较多的字母应优先成对输出并夹一个较少的，以免局部堆积。 $a > b$ 时放 aab， $b > a$ 时放 bba，相等放 ab，最后把剩余单字母接上。

循环构造字符串，当 $a$ 和 $b$ 都大于 0 时：

如果 $a > b$ ，添加字符串 "aab"
如果 $b > a$ ，添加字符串 "bba"
如果 $a = b$ ，添加字符串 "ab"

循环结束，若 $a$ 有剩余，则添加 $a$ 个字符串 "a"；若 $b$ 有剩余，则添加 $b$ 个字符串 "b"。

时间复杂度 $O (a + b)$ 。

func strWithout3a3b(a int, b int) string {
	var ans strings.Builder
	for a > 0 && b > 0 {
		if a > b {
			ans.WriteString("aab")
			a -= 2
			b -= 1
		} else if a < b {
			ans.WriteString("bba")
			a -= 1
			b -= 2
		} else {
			ans.WriteString("ab")
			a--
			b--
		}
	}
	if a > 0 {
		ans.WriteString(strings.Repeat("a", a))
	}
	if b > 0 {
		ans.WriteString(strings.Repeat("b", b))
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

LeetCode Go · 贪心（2） ​

649. Dota2 参议院 ​

659. 分割数组为连续子序列 ​

670. 最大交换 ​

680. 验证回文串 II ​

738. 单调递增的数字 ​

757. 设置交集大小至少为2 ​

763. 划分字母区间 ​

767. 重构字符串 ​

768. 最多能完成排序的块 II ​

769. 最多能完成排序的块 ​

781. 森林中的兔子 ​

807. 保持城市天际线 ​

826. 安排工作以达到最大收益 ​

846. 一手顺子 ​

857. 雇佣 K 名工人的最低成本 ​

860. 柠檬水找零 ​

861. 翻转矩阵后的得分 ​

870. 优势洗牌 ​

881. 救生艇 ​

910. 最小差值 II ​

921. 使括号有效的最少添加 ​

936. 戳印序列 ​

942. 增减字符串匹配 ​

945. 使数组唯一的最小增量 ​

948. 令牌放置 ​

954. 二倍数对数组 ​

955. 删列造序 II ​

969. 煎饼排序 ​

976. 三角形的最大周长 ​

984. 不含 AAA 或 BBB 的字符串 ​

继续阅读

LeetCode Go · 贪心（2）

649. Dota2 参议院

659. 分割数组为连续子序列

670. 最大交换

680. 验证回文串 II

738. 单调递增的数字

757. 设置交集大小至少为2

763. 划分字母区间

767. 重构字符串

768. 最多能完成排序的块 II

769. 最多能完成排序的块

781. 森林中的兔子

807. 保持城市天际线

826. 安排工作以达到最大收益

846. 一手顺子

857. 雇佣 K 名工人的最低成本

860. 柠檬水找零

861. 翻转矩阵后的得分

870. 优势洗牌

881. 救生艇

910. 最小差值 II

921. 使括号有效的最少添加

936. 戳印序列

942. 增减字符串匹配

945. 使数组唯一的最小增量

948. 令牌放置

954. 二倍数对数组

955. 删列造序 II

969. 煎饼排序

976. 三角形的最大周长

984. 不含 AAA 或 BBB 的字符串