LeetCode Go · 贪心（4）

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

来源与许可

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

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

1403. 非递增顺序的最小子序列

简单1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。

与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。

 

示例 1：

输入：nums = [4,3,10,9,8]
输出：[10,9] 
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。 

示例 2：

输入：nums = [4,4,7,6,7]
输出：[7,7,6] 
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。  

 

提示：

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

方法一：排序 · Go 实现

思考

$n\le 500$，枚举全部子序列并比较其和与补集之和是可行的，但需同时满足长度最短、元素之和最大、非递增输出，枚举后还要排序筛选。

要在和超过其余元素的前提下尽量短，应优先取最大的若干个数。将数组降序扫描，累加和 $t$，一旦 $t>s-t$ 即得到满足条件的最短子序列，且已按非递增排列。

我们可以先对数组 $nums$ 按照从大到小的顺序排序，然后依次从大到小加入数组中的元素，每次加入后判断当前元素之和是否大于剩余元素之和，如果大于则返回当前数组。

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

func minSubsequence(nums []int) (ans []int) {
	sort.Ints(nums)
	s, t := 0, 0
	for _, x := range nums {
		s += x
	}
	for i := len(nums) - 1; ; i-- {
		t += nums[i]
		ans = append(ans, nums[i])
		if t > s-t {
			return
		}
	}
}

力扣原题 · Doocs 题解来源

1405. 最长快乐字符串

中等1 种解法

标签：贪心、字符串、堆（优先队列）

题目、示例与约束

如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

• s 是一个尽可能长的快乐字符串。
• s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
• s 中只含有 'a'、'b' 、'c' 三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 ""。

 

示例 1：

输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。

示例 2：

输入：a = 2, b = 2, c = 1
输出："aabbc"

示例 3：

输入：a = 7, b = 1, c = 0
输出："aabaa"
解释：这是该测试用例的唯一正确答案。

 

提示：

• 0 <= a, b, c <= 100
• a + b + c > 0

方法一：贪心 + 优先队列 · Go 实现

思考

$a+b+c\le 300$，搜索所有合法串可以做，但最优解具有明确的局部规则：应尽量使用剩余次数最多的字母，同时禁止连续三个相同字符。

若当前结尾已是两个相同字母，则必须改用次多的字母打断。用大根堆按剩余次数取顶，不合法时改取堆中下一个，用完再将剩余次数压回。

当无法再放入任何字母而不破坏约束时停止，得到的即最长快乐字符串。

贪心，优先选择剩余最多的字符，通过优先队列或排序，确保每次选到的字符都是剩余最多的（为了避免出现连续 3 个一样的字符，一些情况需要选择剩余第二多的字符）。

type pair struct {
	c   byte
	num int
}

type hp []pair

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

func longestDiverseString(a int, b int, c int) string {
	var h hp
	if a > 0 {
		heap.Push(&h, pair{'a', a})
	}
	if b > 0 {
		heap.Push(&h, pair{'b', b})
	}
	if c > 0 {
		heap.Push(&h, pair{'c', c})
	}

	var ans []byte
	for len(h) > 0 {
		cur := heap.Pop(&h).(pair)
		if len(ans) >= 2 && ans[len(ans)-1] == cur.c && ans[len(ans)-2] == cur.c {
			if len(h) == 0 {
				break
			}
			next := heap.Pop(&h).(pair)
			ans = append(ans, next.c)
			if next.num > 1 {
				next.num--
				heap.Push(&h, next)
			}
			heap.Push(&h, cur)
		} else {
			ans = append(ans, cur.c)
			if cur.num > 1 {
				cur.num--
				heap.Push(&h, cur)
			}
		}
	}

	return string(ans)
}

力扣原题 · Doocs 题解来源

1414. 和为 K 的最少斐波那契数字数目

中等1 种解法

标签：贪心、数学

题目、示例与约束

给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

• F₁ = 1
• F₂ = 1
• F_n = F_n-1 + F_n-2 ， 其中 n > 2 。

数据保证对于给定的 k ，一定能找到可行解。

 

示例 1：

输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。

示例 2：

输入：k = 10
输出：2 
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。

示例 3：

输入：k = 19
输出：3 
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。

 

提示：

• 1 <= k <= 10^9

方法一：贪心 · Go 实现

思考

$k\le {10}^9$，完全背包式枚举斐波那契数的组合次数过多。斐波那契数列本身很短，且任意正整数都可写成互不相同的斐波那契数之和（Zeckendorf）。

每次减去不超过 $k$ 的最大斐波那契数是最优的：若还能再用前一项，则当初应改取更大的后一项。先递推到刚超过 $k$，再回退贪心减。

我们可以每次贪心地选取一个不超过 $k$ 的最大的斐波那契数，然后将 $k$ 减去该数，答案加一，一直循环，直到 $k=0$ 为止。

由于每次贪心地选取了最大的不超过 $k$ 的斐波那契数，假设为 $b$，前一个数为 $a$，后一个数为 $c$。将 $k$ 减去 $b$，得到的结果，一定小于 $a$，也即意味着，我们选取了 $b$ 之后，一定不会选到 $a$。这是因为，如果能选上 $a$，那么我们在前面就可以贪心地选上 $b$ 的下一个斐波那契数 $c$，这不符合我们的假设。因此，我们在选取 $b$ 之后，可以贪心地减小斐波那契数。

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

func findMinFibonacciNumbers(k int) (ans int) {
	a, b := 1, 1
	for b <= k {
		c := a + b
		a = b
		b = c
	}

	for k > 0 {
		if k >= b {
			k -= b
			ans++
		}
		c := b - a
		b = a
		a = c
	}
	return
}

力扣原题 · Doocs 题解来源

1432. 改变一个整数能得到的最大差值

中等1 种解法

标签：贪心、数学

题目、示例与约束

给你一个整数 num 。你可以对它进行以下步骤共计 两次：

• 选择一个数字 x (0 <= x <= 9).
• 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
• 将 num 中所有出现 x 的数位都用 y 替换。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

注意，a 和 b 必须不能 含有前导 0，并且 不为 0。

 

示例 1：

输入：num = 555
输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888

示例 2：

输入：num = 9
输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8

示例 3：

输入：num = 123456
输出：820000

示例 4：

输入：num = 10000
输出：80000

示例 5：

输入：num = 9288
输出：8700

 

提示：

• 1 <= num <= 10^8

方法一：贪心 · Go 实现

思考

$num\le {10}^8$，数位很少。一次替换会改写所有相同数字，要让差值最大，应分别构造替换后的最大数与最小数。

最大数：从高位找到第一个不是 $9$ 的数字，把它全部换成 $9$。最小数：若首位不是 $1$，把该数字全换成 $1$；否则在后续位找一个不是 $0$ 或 $1$ 的数字换成 $0$，以免出现前导零或与首位冲突。

要想得到最大差值，那么我们应该拿到最大值与最小值，这样差值最大。

因此，我们先从高到低枚举 $\mathit{\text{nums}}$ 每个位置上的数，如果数字不为 9，就将所有该数字替换为 9，得到最大整数 $a$。

接下来，我们再从高到低枚举 $\mathit{\text{nums}}$ 每个位置上的数，首位不能为 0，因此如果首位不为 1，我们将其替换为 1；如果非首位，且数字不与首位相同，我们将其替换为 0，得到最大整数 $b$。

答案为差值 $a-b$。

时间复杂度 $O(\log \mathit{\text{num}})$，空间复杂度 $O(\log \mathit{\text{num}})$。其中 $\mathit{\text{nums}}$ 为给定整数。

func maxDiff(num int) int {
	a, b := num, num
	s := strconv.Itoa(num)
	for i := range s {
		if s[i] != '9' {
			a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
			break
		}
	}
	if s[0] > '1' {
		b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
	} else {
		for i := 1; i < len(s); i++ {
			if s[i] != '0' && s[i] != '1' {
				b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
				break
			}
		}
	}
	return a - b
}

力扣原题 · Doocs 题解来源

1433. 检查一个字符串是否可以打破另一个字符串

中等1 种解法

标签：贪心、字符串、排序

题目、示例与约束

给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1  的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

 

示例 1：

输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。

示例 2：

输入：s1 = "abe", s2 = "acd"
输出：false 
解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。

示例 3：

输入：s1 = "leetcodee", s2 = "interview"
输出：true

 

提示：

• s1.length == n
• s2.length == n
• 1 <= n <= 10^5
• 所有字符串都只包含小写英文字母。

方法一：排序 · Go 实现

思考

$n\le {10}^5$，不能枚举排列。一方能打破另一方，当且仅当存在一种对应，使每个位置都不小于对方。

两边同时升序后逐位比较：若始终 $s1[i]\ge s2[i]$ 或始终相反，则存在这样的排列。排序后的配对即贪心最优。

将字符串 $s1$, $s2$ 分别进行升序排序。然后同时遍历两个字符串，对应字符进行大小比较。若对于任意 $i∈[0, n)，都有 $s1[i]\le s2[i]$，或者都有 $s1[i]\ge s2[i]$，则存在一个排列可以打破另一个排列。

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

func checkIfCanBreak(s1 string, s2 string) bool {
	cs1 := []byte(s1)
	cs2 := []byte(s2)
	sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] })
	sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] })
	check := func(cs1, cs2 []byte) bool {
		for i := range cs1 {
			if cs1[i] < cs2[i] {
				return false
			}
		}
		return true
	}
	return check(cs1, cs2) || check(cs2, cs1)
}

力扣原题 · Doocs 题解来源

1465. 切割后面积最大的蛋糕

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：

•  horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离
• verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离

请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 109 + 7 取余 后返回。

 

示例 1：

输入：h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出：4 
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。

示例 2：

输入：h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出：6
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色和黄色的两份蛋糕面积最大。

示例 3：

输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出：9

 

提示：

• 2 <= h, w <= 109
• 1 <= horizontalCuts.length <= min(h - 1, 105)
• 1 <= verticalCuts.length <= min(w - 1, 105)
• 1 <= horizontalCuts[i] < h
• 1 <= verticalCuts[i] < w
• 题目数据保证 horizontalCuts 中的所有元素各不相同
• 题目数据保证 verticalCuts 中的所有元素各不相同

方法一：排序 · Go 实现

思考

蛋糕被切成网格，最大块面积等于最大相邻水平间距乘最大相邻竖直间距。 $h,w$ 很大但切口至多 ${10}^5$，对切口排序并补上边界 $0$ 与 $h$、 $w$，取相邻差的最大值相乘，再模 ${10}^9+7$。

我们先分别对 horizontalCuts 和 verticalCuts 排序，然后分别遍历两个数组，计算相邻两个元素的最大差值，分别记为 $x$ 和 $y$，最后返回 $x\times y$ 即可。

注意要考虑边界情况，即 horizontalCuts 和 verticalCuts 的首尾元素。

时间复杂度 $O(m\log m+n\log n)$，空间复杂度 $O(\log m+\log n)$。其中 $m$ 和 $n$ 分别为 horizontalCuts 和 verticalCuts 的长度。

func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
	horizontalCuts = append(horizontalCuts, []int{0, h}...)
	verticalCuts = append(verticalCuts, []int{0, w}...)
	sort.Ints(horizontalCuts)
	sort.Ints(verticalCuts)
	x, y := 0, 0
	const mod int = 1e9 + 7
	for i := 1; i < len(horizontalCuts); i++ {
		x = max(x, horizontalCuts[i]-horizontalCuts[i-1])
	}
	for i := 1; i < len(verticalCuts); i++ {
		y = max(y, verticalCuts[i]-verticalCuts[i-1])
	}
	return (x * y) % mod
}

力扣原题 · Doocs 题解来源

1481. 不同整数的最少数目

中等1 种解法

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

题目、示例与约束

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

 

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

 

提示：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

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

思考

去掉 $k$ 个数后希望剩下的不同整数尽量少，应优先删出现次数少的。计数后把频次升序，依次用 $k$ 抵消，无法抵消时剩余种类数为尚未删完的个数。

我们用哈希表 $cnt$ 统计数组 $arr$ 中每个整数出现的次数，然后将 $cnt$ 中的值按照从小到大的顺序排序，记录在数组 $nums$ 中。

接下来，我们遍历数组 $nums$，对于当前遍历到的每个值 $nums[i]$，我们将 $k$ 减去 $nums[i]$，如果 $k<0$，则说明我们已经移除了 $k$ 个元素，此时数组中不同整数的最少数目为 $nums$ 的长度减去当前遍历到的下标 $i$，直接返回即可。

若遍历结束，说明我们移除了所有的元素，此时数组中不同整数的最少数目为 $0$。

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

func findLeastNumOfUniqueInts(arr []int, k int) int {
	cnt := map[int]int{}
	for _, x := range arr {
		cnt[x]++
	}
	nums := make([]int, 0, len(cnt))
	for _, v := range cnt {
		nums = append(nums, v)
	}
	sort.Ints(nums)
	for i, v := range nums {
		k -= v
		if k < 0 {
			return len(nums) - i
		}
	}
	return 0
}

力扣原题 · Doocs 题解来源

1488. 避免洪水泛滥

中等1 种解法

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

题目、示例与约束

你的国家有 10⁹ 个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。如果第 n 个湖泊下雨前是 满的 ，这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。

给你一个整数数组 rains ，其中：

• rains[i] > 0 表示第 i 天时，第 rains[i] 个湖泊会下雨。
• rains[i] == 0 表示第 i 天没有湖泊会下雨，你 必须 选择 一个 湖泊并 抽干 这个湖泊的水。

请返回一个数组 ans ，满足：

• ans.length == rains.length
• 如果 rains[i] > 0 ，那么ans[i] == -1 。
• 如果 rains[i] == 0 ，ans[i] 是你第 i 天选择抽干的湖泊。

如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。

请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。

 

示例 1：

输入：rains = [1,2,3,4]
输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。

示例 2：

输入：rains = [1,2,0,0,2,1]
输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

示例 3：

输入：rains = [1,2,0,1,2]
输出：[]
解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。

 

提示：

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

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

思考

$n\le {10}^5$，同一湖泊第二次下雨前必须抽干，否则洪水。晴天应留给「最近将再次下雨且尚未抽干」的湖，且抽干日必须在上次下雨之后。

有序集合保存晴天下标，哈希表记下每湖上次下雨日。再次下雨时在晴天中二分出第一次晚于该日的空档；没有则失败。未使用的晴天填 $1$。

我们将所有晴天都存入 $sunny$ 数组或者有序集合中，使用哈希表 $rainy$ 记录每个湖泊最近一次下雨的日期。初始化答案数组 $ans$ 每个元素为 $-1$。

接下来，我们遍历 $rains$ 数组。对于每个下雨的日期 $i$，如果 $rainy[rains[i]]$ 存在，说明该湖泊在之前下过雨，那么我们需要找到 $sunny$ 数组中第一个大于 $rainy[rains[i]]$ 的日期，将其替换为下雨的日期，否则说明无法阻止洪水，返回空数组。对于没下雨的日期 $i$，我们将 $i$ 存入 $sunny$ 数组中，并且将 $ans[i]$ 置为 $1$。

遍历结束，返回答案数组。

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

func avoidFlood(rains []int) []int {
	n := len(rains)
	ans := make([]int, n)
	for i := range ans {
		ans[i] = -1
	}

	sunny := redblacktree.New[int, struct{}]()
	rainy := map[int]int{}

	for i, v := range rains {
		if v > 0 {
			if last, ok := rainy[v]; ok {
				node, found := sunny.Ceiling(last + 1)
				if !found {
					return []int{}
				}
				t := node.Key
				ans[t] = v
				sunny.Remove(t)
			}
			rainy[v] = i
		} else {
			sunny.Put(i, struct{}{})
			ans[i] = 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个数组 nums 。

每次操作你可以选择 nums 中的任意一个元素并将它改成 任意值 。

在 执行最多三次操作后 ，返回 nums 中最大值与最小值的最小差值。

 

示例 1：

输入：nums = [5,3,2,4]
输出：0
解释：我们最多可以走 3 步。
第一步，将 2 变为 3 。 nums 变成 [5,3,3,4] 。
第二步，将 4 改为 3 。 nums 变成 [5,3,3,3] 。
第三步，将 5 改为 3 。 nums 变成 [3,3,3,3] 。
执行 3 次移动后，最小值和最大值之间的差值为 3 - 3 = 0 。

示例 2：

输入：nums = [1,5,0,10,14]
输出：1
解释：我们最多可以走 3 步。
第一步，将 5 改为 0 。 nums变成 [1,0,0,10,14] 。
第二步，将 10 改为 0 。 nums变成 [1,0,0,0,14] 。
第三步，将 14 改为 1 。 nums变成 [1,0,0,0,1] 。
执行 3 步后，最小值和最大值之间的差值为 1 - 0 = 1 。
可以看出，没有办法可以在 3 步内使差值变为0。

示例 3：

输入：nums = [3,100,20]
输出：0
解释：我们最多可以走 3 步。
第一步，将 100 改为 7 。 nums 变成 [3,7,20] 。
第二步，将 20 改为 7 。 nums 变成 [3,7,7] 。
第三步，将 3 改为 7 。 nums 变成 [7,7,7] 。
执行 3 步后，最小值和最大值之间的差值是 7 - 7 = 0。

 

提示：

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

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

思考

最多改三个数，使最大值与最小值之差尽量小。 $n\le {10}^5$，不能枚举被改的三元组。长度不足 $5$ 时改三个数后只剩至多一个有效值，差为 $0$。

排序之后，未改动的值构成一段连续区间，三次修改等价于从两端一共丢掉三个极端值。枚举左边丢掉 $l\in \{0,1,2,3\}$ 个、右边丢掉 $3-l$ 个，取 $nums[n-1-r]-nums[l]$ 的最小值即可。

我们可以先判断数组长度是否小于 $5$，如果小于 $5$，那么直接返回 $0$。

否则，我们将数组排序，然后贪心地选择数组左边最小的 $l=[0,..3]$ 个数和右边最小的 $r=3-l$ 个数，取其中最小的差值 $nums[n-1-r]-nums[l]$ 即可。

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

相似题目：

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

func minDifference(nums []int) int {
	n := len(nums)
	if n < 5 {
		return 0
	}
	sort.Ints(nums)
	ans := 1 << 60
	for l := 0; l <= 3; l++ {
		r := 3 - l
		ans = min(ans, nums[n-1-r]-nums[l])
	}
	return ans
}

力扣原题 · Doocs 题解来源

1520. 最多的不重叠子字符串

困难1 种解法

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

题目、示例与约束

给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

1. 这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[x..y] ，要么 j < x 要么 i > y 。
2. 如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。

请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。

请注意，你可以以 任意 顺序返回最优解的子字符串。

 

示例 1：

输入：s = "adefaddaccc"
输出：["e","f","ccc"]
解释：下面为所有满足第二个条件的子字符串：
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。如果我们选择 "adefadda" ，剩下子字符串中我们只可以选择 "ccc" ，它是唯一不重叠的子字符串，所以答案为 2 。同时我们可以发现，选择 "ef" 不是最优的，因为它可以被拆分成 2 个子字符串。所以最优解是选择 ["e","f","ccc"] ，答案为 3 。不存在别的相同数目子字符串解。

示例 2：

输入：s = "abbaccd"
输出：["d","bb","cc"]
解释：注意到解 ["d","abba","cc"] 答案也为 3 ，但它不是最优解，因为它的总长度更长。

 

提示：

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

方法一：贪心 · Go 实现

思考

要选出尽量多段互不重叠的子串，且每段必须覆盖其中每个字符在整个字符串里的全部出现。 $n\le {10}^5$，不能枚举全部子串再验证。

每个字符有确定的首次与末次出现。从某一左端出发，不断把区间扩大到内部字符的最右出现，得到一条不可再缩的合法段。所有这样的极小段构成区间图，按右端点贪心选取互不重叠者，即可同时达到数量最多且总长度最短。

我们先用数组或哈希表 $\mathit{\text{first}}$ 和 $\mathit{\text{last}}$ 记录每个字母在 $s$ 中首次和末次出现的下标。

接下来枚举每一个出现过的字母 $c$，以 $\mathit{\text{first}}[c]$ 作为候选左端点 $l$，以 $\mathit{\text{last}}[c]$ 作为初始右端点 $r$。从 $l$ 向右扫描到 $r$，对扫到的每个字母 $ch$：

• 若 $\mathit{\text{first}}[ch]<l$，说明该字母在 $l$ 之前还出现过，当前区间无法覆盖其全部出现，这段候选不合法，直接放弃；
• 否则将 $r$ 更新为 $max(r,\mathit{\text{last}}[ch])$，把该字母的全部出现纳入区间。

若扫描能够顺利结束，则得到一段合法子串区间 $[l,r]$。

可以证明，这些合法区间之间只可能互不相交或相互包含，不会部分重叠。因此我们将所有合法区间按右端点升序排序，再贪心选取：用变量 $\mathit{\text{end}}$ 记录上一个已选区间的右端点，初始为 $-1$。从左到右遍历排序后的区间，若当前区间左端点大于 $\mathit{\text{end}}$，则将其对应子串加入答案，并更新 $\mathit{\text{end}}$。

按右端点排序保证了每次选择的都是结束最早的区间，从而可以选出数量最多的互不重叠子串；由于相互包含时更短的区间右端点更小，也会被优先选中，因此总长度同时最短。

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

func maxNumOfSubstrings(s string) (ans []string) {
	first := [26]int{}
	last := [26]int{}
	for i := range first {
		first[i] = -1
	}
	for i := range s {
		x := int(s[i] - 'a')
		if first[x] == -1 {
			first[x] = i
		}
		last[x] = i
	}
	var segs [][2]int
	for x, l := range first {
		if l == -1 {
			continue
		}
		r := last[x]
		i := l
		for ; i <= r; i++ {
			y := int(s[i] - 'a')
			if first[y] < l {
				break
			}
			r = max(r, last[y])
		}
		if i > r {
			segs = append(segs, [2]int{l, r})
		}
	}
	sort.Slice(segs, func(i, j int) bool { return segs[i][1] < segs[j][1] })
	end := -1
	for _, e := range segs {
		l, r := e[0], e[1]
		if l > end {
			ans = append(ans, s[l:r+1])
			end = r
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1529. 最少的后缀翻转次数

中等1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个长度为 n 、下标从 0 开始的二进制字符串 target 。你自己有另一个长度为 n 的二进制字符串 s ，最初每一位上都是 0 。你想要让 s 和 target 相等。

在一步操作，你可以选择下标 i（0 <= i < n）并翻转在 闭区间 [i, n - 1] 内的所有位。翻转意味着 '0' 变为 '1' ，而 '1' 变为 '0' 。

返回使 s 与 target 相等需要的最少翻转次数。

 

示例 1：

输入：target = "10111"
输出：3
解释：最初，s = "00000" 。
选择下标 i = 2: "00000" -> "00111"
选择下标 i = 0: "00111" -> "11000"
选择下标 i = 1: "11000" -> "10111"
要达成目标，需要至少 3 次翻转。

示例 2：

输入：target = "101"
输出：3
解释：最初，s = "000" 。
选择下标 i = 0: "000" -> "111"
选择下标 i = 1: "111" -> "100"
选择下标 i = 2: "100" -> "101"
要达成目标，需要至少 3 次翻转。

示例 3：

输入：target = "00000"
输出：0
解释：由于 s 已经等于目标，所以不需要任何操作

 

提示：

• n == target.length
• 1 <= n <= 105
• target[i] 为 '0' 或 '1'

方法一：贪心 · Go 实现

思考

操作是翻转某个后缀，要把全 $0$ 变成 $target$。 $n\le {10}^5$，不能对每个后缀模拟。当前缀已经与 $target$ 一致时，下一次翻转只应发生在下一个与当前状态不同的位置。

从左到右扫描：翻转次数的奇偶决定该位当前值。若与 $target[i]$ 不同，必须在 $i$ 处再翻一次后缀。这样每次翻转都修正在此之前无法改写的最左错误位，次数最少。

我们从左到右遍历字符串 $\mathit{\text{target}}$，用变量 $\mathit{\text{ans}}$ 记录翻转次数。 当遍历到下标 $i$ 时，如果当前的翻转次数 $\mathit{\text{ans}}$ 的奇偶性与 $\mathit{\text{target}}[i]$ 不同，则需要在下标 $i$ 处进行一次翻转操作，将 $\mathit{\text{ans}}$ 加 $1$。

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

func minFlips(target string) int {
	ans := 0
	for _, c := range target {
		v := int(c - '0')
		if ((ans & 1) ^ v) != 0 {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1536. 排布二进制网格的最少交换次数

中等1 种解法

标签：贪心、数组、矩阵

题目、示例与约束

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

 

示例 1：

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

示例 2：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

示例 3：

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

 

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 200
• grid[i][j] 要么是 0 要么是 1 。

方法一：贪心 · Go 实现

思考

通过交换相邻行，使第 $i$ 行在对角线右侧全为 $0$。只关心每行最右一个 $1$ 的位置：该位置 $\le i$ 时第 $i$ 行才合法。 $n\le 200$，可按行贪心。

对每个 $i$，在尚未使用的行中找第一个最右 $1$ 下标 $\le i$ 的行 $k$，再通过相邻交换把它换到第 $i$ 行，代价为 $k-i$。若不存在这样的行则无解。先满足更靠上的行不会妨碍后面，因为后面需要的尾零更少。

我们逐行处理，对于第 $i$ 行，最后一个 $1$ 所在的位置必须小于等于 $i$，我们在 $[i,n)$ 中找到第一个满足条件的行，记为 $k$。然后从第 $k$ 行开始，依次向上交换相邻的两行，直到第 $i$ 行。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是网格的边长。

func minSwaps(grid [][]int) (ans int) {
	n := len(grid)
	pos := make([]int, n)
	for i := range pos {
		pos[i] = -1
	}
	for i := 0; i < n; i++ {
		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 1 {
				pos[i] = j
				break
			}
		}
	}
	for i := 0; i < n; i++ {
		k := -1
		for j := i; j < n; j++ {
			if pos[j] <= i {
				ans += j - i
				k = j
				break
			}
		}
		if k == -1 {
			return -1
		}
		for ; k > i; k-- {
			pos[k], pos[k-1] = pos[k-1], pos[k]
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1541. 平衡括号字符串的最少插入次数

中等1 种解法

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

题目、示例与约束

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

• 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
• 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

 

示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。

示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。

示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

 

提示：

• 1 <= s.length <= 10^5
• s 只包含 '(' 和 ')' 。

方法一：贪心 · Go 实现

思考

合法括号要求每个 '(' 配两个连续的 ')'。 $n\le {10}^5$，反复扫描插入位置不如一次贪心。

从左到右维护尚未匹配的左括号个数 $x$。遇到 '(' 则 $x$ 加一；遇到 ')' 时，若不是成对则先插入一个右括号。此时若没有左括号可配，再插入一个 '('，否则消耗一个 $x$。扫完后每个剩余的左括号还要补两个 ')'。

我们用 $x$ 表示字符串中待匹配的左括号的数量，初始时为 $0$。遍历字符串 $s$：

如果遇到左括号，则 $x$ 的值加 $1$；如果遇到右括号，我们分情况讨论：

• 如果有两个连续的右括号，那么我们先让指针往后移动一位；否则，我们需要插入一个右括号，使得出现两个连续的右括号，因此插入次数加 $1$；
• 如果 $x=0$，说明当前没有待匹配的左括号，我们需要插入一个左括号，用于匹配上面准备好的两个连续的右括号，因此插入次数加 $1$；否则，我们让 $x$ 的值减 $1$。

然后指针往后移动一位，继续下一次遍历。

遍历结束后，如果 $x=0$，说明字符串已经平衡，返回插入次数；否则，说明字符串中有待匹配的左括号，我们需要再插入 $2\times x$ 个右括号，使得字符串变成平衡字符串，返回插入次数。

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

func minInsertions(s string) int {
	ans, x, n := 0, 0, len(s)
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			x++
		} else {
			if i < n-1 && s[i+1] == ')' {
				i++
			} else {
				ans++
			}
			if x == 0 {
				ans++
			} else {
				x--
			}
		}
	}
	ans += x << 1
	return ans
}

力扣原题 · Doocs 题解来源

1546. 和为目标值且不重叠的非空子数组的最大数目

中等1 种解法

标签：贪心、数组、哈希表、前缀和

题目、示例与约束

给你一个数组 nums 和一个整数 target 。

请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。

 

示例 1：

输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。

示例 2：

输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

示例 3：

输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3

示例 4：

输入：nums = [0,0,0], target = 0
输出：3

 

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

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

思考

选出尽量多段互不重叠、和为 $target$ 的子数组。 $n\le {10}^5$，区间 DP 不可行。若两段相交，留下更靠左结束的那段不会减少后续可选数量。

从左到右用前缀和哈希表找最早结束的和为 $target$ 的段，计入答案后从下一段重新开始。贪心保证每段都尽量短、尽早结束，从而给后面留下更多空间。

我们遍历数组 $nums$，利用前缀和 + 哈希表的方法，寻找和为 $target$ 的子数组，若找到，则答案加一，然后我们将前缀和置为 $0$，继续遍历数组 $nums$，直到遍历完整个数组。

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

func maxNonOverlapping(nums []int, target int) (ans int) {
	n := len(nums)
	for i := 0; i < n; i++ {
		s := 0
		vis := map[int]bool{0: true}
		for ; i < n; i++ {
			s += nums[i]
			if vis[s-target] {
				ans++
				break
			}
			vis[s] = true
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1558. 得到目标数组的最少函数调用次数

中等1 种解法

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

题目、示例与约束

给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。

请你返回将 arr 变成 nums 的最少函数调用次数。

答案保证在 32 位有符号整数以内。

 

示例 1：

输入：nums = [1,5]
输出：5
解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 。

示例 2：

输入：nums = [2,2]
输出：3
解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。
总操作次数为： 2 + 1 = 3 。

示例 3：

输入：nums = [4,2,5]
输出：6
解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums 数组）。

示例 4：

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

示例 5：

输入：nums = [2,4,8,16]
输出：8

 

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

方法一 · Go 实现

思考

从全零数组出发，操作为「某一位加一」或「全体乘二」，要得到 $nums$。 $n\le {10}^5$、 $nums[i]\le {10}^9$，不能按值模拟。乘二相当于全体同时左移，加一相当于把某数的某个 $1$ 比特写上。

每个数 $v$ 需要 $v$ 的二进制中 $1$ 的个数次加一；全体共享的乘二次数由最大值的比特长度减一决定。两者相加即为最少调用次数。

func minOperations(nums []int) int {
	ans, mx := 0, 0
	for _, v := range nums {
		mx = max(mx, v)
		for v > 0 {
			ans += v & 1
			v >>= 1
		}
	}
	if mx > 0 {
		for mx > 0 {
			ans++
			mx >>= 1
		}
		ans--
	}
	return ans
}

力扣原题 · Doocs 题解来源

1561. 你可以获得的最大硬币数目

中等1 种解法

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

题目、示例与约束

有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

• 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
• Alice 将会取走硬币数量最多的那一堆。
• 你将会取走硬币数量第二多的那一堆。
• Bob 将会取走最后一堆。
• 重复这个过程，直到没有更多硬币。

给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。

返回你可以获得的最大硬币数目。

 

示例 1：

输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。

示例 2：

输入：piles = [2,4,5]
输出：4

示例 3：

输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18

 

提示：

• 3 <= piles.length <= 10^5
• piles.length % 3 == 0
• 1 <= piles[i] <= 10^4

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

思考

三人每次各取一堆，Alice 拿当前最大、我们拿次大、Bob 拿最小，求我们的总和。 $n$ 达 ${10}^5$，不能按轮模拟比较。

排序后 Bob 固定拿走最小的三分之一。剩余堆从左到右交替给 Alice 和我们，我们拿到的是从下标 $n/3$ 起每隔一个的那些。对其求和即可。

为了让我们获得的硬币数量最多，我们可以贪心地让 Bob 拿走最少的 $n$ 堆硬币。我们每次先让 Alice 拿走最多的一堆硬币，然后让我们拿走第二多的一堆硬币，依次循环，直到没有硬币可拿。

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

func maxCoins(piles []int) (ans int) {
	sort.Ints(piles)
	for i := len(piles) / 3; i < len(piles); i += 2 {
		ans += piles[i]
	}
	return
}

力扣原题 · Doocs 题解来源

1564. 把箱子放进仓库里 I 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给定两个正整数数组 boxes 和 warehouse ，分别包含单位宽度的箱子的高度，以及仓库中 n 个房间各自的高度。仓库的房间分别从 0 到 n - 1 自左向右编号， warehouse[i] （索引从 0 开始）是第 i 个房间的高度。

箱子放进仓库时遵循下列规则：

• 箱子不可叠放。
• 你可以重新调整箱子的顺序。
• 箱子只能从左向右推进仓库中。
• 如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。

你最多可以在仓库中放进多少个箱子？

 

示例 1：

输入：boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
输出：3
解释：

我们可以先把高度为 1 的箱子放入 4 号房间，然后再把高度为 3 的箱子放入 1 号、 2 号或 3 号房间，最后再把高度为 4 的箱子放入 0 号房间。
我们不可能把所有 4 个箱子全部放进仓库里。

示例 2：

输入：boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
输出：3
解释：

我们注意到，不可能把高度为 4 的箱子放入仓库中，因为它不能通过高度为 3 的房间。
而且，对于最后两个房间 2 号和 3 号来说，只有高度为 1 的箱子可以放进去。
我们最多可以放进 3 个箱子，如上图所示。黄色的箱子也可以放入 2 号房间。
交换橙色和绿色箱子的位置，或是将这两个箱子与红色箱子交换位置，也是可以的。

示例 3：

输入：boxes = [1,2,3], warehouse = [1,2,3,4]
输出：1
解释：由于第一个房间的高度为 1，我们只能放进高度为 1 的箱子。

 

提示：

• n == warehouse.length
• 1 <= boxes.length, warehouse.length <= 10^5
• 1 <= boxes[i], warehouse[i] <= 10^9

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

思考

箱子只能从仓库左侧依次推入，且不能翻越更矮的房间。 $n\le {10}^5$，不能枚举装箱排列。房间 $i$ 能容纳的高度受其左侧最矮房间限制。

预处理 $left[i]=min(warehouse[0..i])$，再把箱子升序排列。小箱子优先放入尽量靠里、仍够高的房间：右指针从最深处左移到第一个 $left[j]\ge boxes[i]$ 的位置，放入后两指针各进一步。这样大箱子留在外侧更高的房间。

我们可以先对仓库的房间进行预处理，得到一个数组 $left$，其中 $left[i]$ 表示下标 $i$ 可以放入的最大箱子高度。

然后对箱子的高度进行排序，从小到大依次放入仓库中。我们使用两个指针 $i$ 和 $j$ 分别指向箱子的第一个位置以及仓库的最后一个位置，如果 $left[j]<boxes[i]$，说明当前仓库无法放入箱子 $i$，我们将指针 $j$ 循环向左移动，直到 $left[j]\ge boxes[i]$ 或者 $j<0$。如果此时 $j<0$，说明仓库已经没有空间可以放入箱子 $i$，我们可以直接退出循环。否则说明仓库可以放入箱子 $i$，我们将指针 $i$ 循环向右移动，指针 $j$ 循环向左移动。继续进行上述操作，直到指针 $i$ 超出箱子的范围。

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

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

func maxBoxesInWarehouse(boxes []int, warehouse []int) int {
	n := len(warehouse)
	left := make([]int, n)
	left[0] = warehouse[0]
	for i := 1; i < n; i++ {
		left[i] = min(left[i-1], warehouse[i])
	}
	sort.Ints(boxes)
	i, j := 0, n-1
	for i < len(boxes) {
		for j >= 0 && left[j] < boxes[i] {
			j--
		}
		if j < 0 {
			break
		}
		i, j = i+1, j-1
	}
	return i
}

力扣原题 · Doocs 题解来源

1580. 把箱子放进仓库里 II 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给定两个正整数数组 boxes 和 warehouse ，分别包含单位宽度的箱子的高度，以及仓库中n个房间各自的高度。仓库的房间分别从0 到 n - 1自左向右编号，warehouse[i]（索引从 0 开始）是第 i 个房间的高度。

箱子放进仓库时遵循下列规则：

• 箱子不可叠放。
• 你可以重新调整箱子的顺序。
• 箱子可以从任意方向（左边或右边）推入仓库中。
• 如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。

你最多可以在仓库中放进多少个箱子？

 

示例 1:

输入: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
输出: 4
解释:

我们可以按如下顺序推入箱子:
1- 从左边或右边把黄色箱子推入2号房间；
2- 从右边把橙色箱子推入3号房间；
3- 从左边把绿色箱子推入1号房间；
4- 从左边把红色箱子推入0号房间；
还有其他方式推入4个箱子，比如交换红色与绿色箱子，或者交换红色与橙色箱子。

示例 2:

输入: boxes = [3,5,5,2], warehouse = [2,1,3,4,5]
输出: 3
解释:

因为只有一个高度大于等于5的房间，所以无法将两个高度为5的箱子都推入仓库。
还有其他方式推入箱子，比如将绿色箱子推入2号房间，或者在绿色及红色箱子之前将橙色箱子推入2号房间。

示例 3:

输入: boxes = [1,2,3], warehouse = [1,2,3,4]
输出: 3

示例 4:

输入: boxes = [4,5,6], warehouse = [3,3,3,3,3]
输出: 0

 

提示:

• n == warehouse.length
• 1 <= boxes.length, warehouse.length <= 105
• 1 <= boxes[i], warehouse[i] <= 109

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

思考

箱子可从仓库两端推入，仍不能越过更矮的房间。 $n\le {10}^5$，不能枚举左右入口的分配。房间 $i$ 的有效高度是自身与「从某一端进来时沿途最矮处」的较小者，而两端取较大的那条通路。

预处理左侧沿途最小高度 $left[i]$ 与右侧 $right[i]$，再令房间容量为 $min(warehouse[i],max(left[i],right[i]))$。之后与箱子一并排序，小箱子优先匹配当前最矮仍够高的房间。

我们先对仓库进行预处理，得到每个房间的最大高度，然后对箱子和仓库进行排序，从最小的箱子开始，从最小的房间开始，如果当前房间的高度大于等于当前箱子的高度，则可以将当前箱子放入当前房间，否则继续寻找下一个房间。

最后返回可以放入的箱子数量。

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

func maxBoxesInWarehouse(boxes []int, warehouse []int) (ans int) {
	n := len(warehouse)
	left := make([]int, n)
	right := make([]int, n)
	const inf = 1 << 30
	left[0] = inf
	right[n-1] = inf
	for i := 1; i < n; i++ {
		left[i] = min(left[i-1], warehouse[i-1])
	}
	for i := n - 2; i >= 0; i-- {
		right[i] = min(right[i+1], warehouse[i+1])
	}
	for i := 0; i < n; i++ {
		warehouse[i] = min(warehouse[i], max(left[i], right[i]))
	}
	sort.Ints(boxes)
	sort.Ints(warehouse)
	i := 0
	for _, x := range boxes {
		for i < n && warehouse[i] < x {
			i++
		}
		if i == n {
			break
		}
		ans++
		i++
	}
	return
}

力扣原题 · Doocs 题解来源

1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

困难1 种解法

标签：贪心、字符串、排序

题目、示例与约束

给你两个字符串 s 和 t ，请你通过若干次以下操作将字符串 s 转化成字符串 t ：

• 选择 s 中一个 非空 子字符串并将它包含的字符就地 升序 排序。

比方说，对下划线所示的子字符串进行操作可以由 "14234" 得到 "12344" 。

如果可以将字符串 s 变成 t ，返回 true 。否则，返回 false 。

一个 子字符串 定义为一个字符串中连续的若干字符。

 

示例 1：

输入：s = "84532", t = "34852"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"84532" （从下标 2 到下标 3）-> "84352"
"84352" （从下标 0 到下标 2） -> "34852"

示例 2：

输入：s = "34521", t = "23415"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"34521" -> "23451"
"23451" -> "23415"

示例 3：

输入：s = "12345", t = "12435"
输出：false

示例 4：

输入：s = "1", t = "2"
输出：false

 

提示：

• s.length == t.length
• 1 <= s.length <= 105
• s 和 t 都只包含数字字符，即 '0' 到 '9' 。

方法一：冒泡排序 · Go 实现

思考

对任意子串排序若干次，问 $s$ 能否变成 $t$。子串排序等价于相邻逆序对的冒泡：较大数字不能越过左侧更小的数字。 $n\le {10}^5$，不能模拟每一次排序。

记下 $s$ 中每个数字的下标队列。按 $t$ 的顺序取出数字 $x$ 的最左出现：若存在更小数字仍停在它左边，则无法把它换到当前位。否则弹出该下标继续。频次不足也失败。

题目实际上等价于判断：将字符串 $s$ 中任意长度为 $2$ 的子字符串采用冒泡排序交换，是否能得到 $t$。

因此我们用一个长度为 $10$ 的数组 $pos$ 记录字符串 $s$ 中每个字符数字的下标，其中 $pos[i]$ 表示数字 $i$ 出现的下标列表，按从小到大排序。

接下来，我们遍历字符串 $t$，对于 $t$ 中的每个字符 $t[i]$，我们转为数字 $x$，我们判断 $pos[x]$ 是否为空，若是，说明字符串 $s$ 中不存在 $t$ 中的数字，直接返回 false。否则，若要将 $pos[x]$ 的第一个位置下标的字符交换到下标 $i$ 的位置，需要满足小于 $x$ 的所有数字的下标均不小于 $pos[x]$ 的第一个位置下标，若不满足，返回 false。否则，我们将 $pos[x]$ 的第一个位置下标弹出，然后继续遍历字符串 $t$。

遍历结束，返回 true。

时间复杂度 $O(n\times C)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 是数字集的大小，本题中 $C=10$。

func isTransformable(s string, t string) bool {
	pos := [10][]int{}
	for i, c := range s {
		pos[c-'0'] = append(pos[c-'0'], i)
	}
	for _, c := range t {
		x := int(c - '0')
		if len(pos[x]) == 0 {
			return false
		}
		for j := 0; j < x; j++ {
			if len(pos[j]) > 0 && pos[j][0] < pos[x][0] {
				return false
			}
		}
		pos[x] = pos[x][1:]
	}
	return true
}

力扣原题 · Doocs 题解来源

1589. 所有排列中的最大和

中等1 种解法

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

题目、示例与约束

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的结果 ，starti 和 endi 数组索引都是 从 0 开始 的。

你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。

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

 

示例 1：

输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。

示例 2：

输入：nums = [1,2,3,4,5,6], requests = [[0,1]]
输出：11
解释：一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。

示例 3：

输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
输出：47
解释：一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。

 

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 105
• 1 <= requests.length <= 105
• requests[i].length == 2
• 0 <= starti <= endi < n

方法一：差分数组 + 排序 + 贪心 · Go 实现

思考

可重排 $nums$，使所有询问区间和的总和最大。 $n$ 与询问数达 ${10}^5$，不能对每个排列求一遍。一个下标被覆盖得越多，就应放越大的数。

差分数组在 $O(1)$ 内给 $[l,r]$ 加一，前缀和后得到每个下标的覆盖次数。将次数与 $nums$ 同序排序后对应相乘再取模，即把最大的值配给最热的位置。

我们观察发现，对于一次查询操作，会返回该查询区间 $[l,r]$ 中的所有元素之和。而题目要求的是所有查询操作的结果之和的最大值，也即是说，我们要累计所有查询操作的结果，使得这些结果之和最大。因此，如果一个下标 $i$ 在查询操作中出现的次数越多，那么我们就应该赋给下标 $i$ 一个较大的值，这样才能使得所有查询操作的结果之和最大。

因此，我们可以用差分数组的思想，统计每个下标在查询操作中出现的次数，然后对这些次数从小到大进行排序，然后对数组 $\mathit{\text{nums}}$ 也从小到大进行排序，这样就能保证每个下标 $i$ 在查询操作中出现的次数越多，该下标对应的值 $\mathit{\text{nums}}[i]$ 就越大。接下来，我们只需要将这些下标对应的值 $\mathit{\text{nums}}[i]$ 与其在查询操作中出现的次数相乘，然后累加起来，就是所有查询操作的结果之和的最大值。

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

func maxSumRangeQuery(nums []int, requests [][]int) (ans int) {
	n := len(nums)
	d := make([]int, n)
	for _, req := range requests {
		l, r := req[0], req[1]
		d[l]++
		if r+1 < n {
			d[r+1]--
		}
	}
	for i := 1; i < n; i++ {
		d[i] += d[i-1]
	}
	sort.Ints(nums)
	sort.Ints(d)
	const mod = 1e9 + 7
	for i, a := range nums {
		b := d[i]
		ans = (ans + a*b) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1605. 给定行和列的和求可行矩阵

中等1 种解法

标签：贪心、数组、矩阵、网络流

题目、示例与约束

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，且该矩阵满足 rowSum 和 colSum 的要求。

请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。

 

示例 1：

输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
      [1,7]]
解释：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
                  [3,5]]

示例 2：

输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
      [6,1,0],
      [2,0,8]]

示例 3：

输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
      [6,0,3]]

示例 4：

输入：rowSum = [1,0], colSum = [1]
输出：[[1],
      [0]]

示例 5：

输入：rowSum = [0], colSum = [0]
输出：[[0]]

 

提示：

• 1 <= rowSum.length, colSum.length <= 500
• 0 <= rowSum[i], colSum[i] <= 108
• sum(rowSum) == sum(colSum)

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

思考

需要构造非负矩阵使各行之和、各列之和分别等于给定数组，且 $\sum \mathit{\text{rowSum}}=\sum \mathit{\text{colSum}}$。逐格搜索填数在 $m,n\le 500$ 下不可行。

对位置 $(i,j)$ 放入 $x=min(\mathit{\text{rowSum}}[i],\mathit{\text{colSum}}[j])$ 并同时扣减对应行、列剩余，剩余问题仍满足行和与列和相等，因而可以继续贪心。

按行优先扫描整张表即可得到一组可行解，不必回溯。

我们可以先初始化一个 $m$ 行 $n$ 列的答案矩阵 $ans$。

接下来，遍历矩阵的每一个位置 $(i,j)$，将该位置的元素设为 $x=min(rowSum[i],colSum[j])$，并将 $rowSum[i]$ 和 $colSum[j]$ 分别减去 $x$。遍历完所有的位置后，我们就可以得到一个满足题目要求的矩阵 $ans$。

以上策略的正确性说明如下：

根据题目的要求，我们知道 $rowSum$ 和 $colSum$ 的和是相等的，那么 $rowSum[0]$ 一定小于等于 $\sum _{j=0}^{n-1}colSum[j]$。所以，在经过 $n$ 次操作后，一定能够使得 $rowSum[0]$ 为 $0$，并且保证对任意 $j\in [0,n-1]$，都有 $colSum[j]\ge 0$。

因此，我们把原问题缩小为一个 $m-1$ 行和 $n$ 列的子问题，继续进行上述的操作，直到 $rowSum$ 和 $colSum$ 中的所有元素都为 $0$，就可以得到一个满足题目要求的矩阵 $ans$。

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

func restoreMatrix(rowSum []int, colSum []int) [][]int {
	m, n := len(rowSum), len(colSum)
	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
	}
	for i := range rowSum {
		for j := range colSum {
			x := min(rowSum[i], colSum[j])
			ans[i][j] = x
			rowSum[i] -= x
			colSum[j] -= x
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1642. 可以到达的最远建筑

中等1 种解法

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

题目、示例与约束

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

• 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
• 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

 

示例 1：

输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。

示例 2：

输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7

示例 3：

输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3

 

提示：

• 1 <= heights.length <= 105
• 1 <= heights[i] <= 106
• 0 <= bricks <= 109
• 0 <= ladders <= heights.length

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

思考

只有上坡消耗砖或梯，梯子应留给最大的若干次爬升。 $n$ 与资源均可达较大规模，需要在线决定。

用小根堆保存已经用梯子覆盖的爬升；堆大小超过梯数时，把最小的一次改用砖。砖不够则停在当前位置。

若全程砖都够，则到达最后一栋。

梯子最好用在高度差较大的地方，因此我们可以将所有的高度差存入优先队列中，每次取出最小的高度差，如果梯子不够用，则用砖块填补，如果砖块不够用，则返回当前位置。

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

func furthestBuilding(heights []int, bricks int, ladders int) int {
	q := hp{}
	n := len(heights)
	for i, a := range heights[:n-1] {
		b := heights[i+1]
		d := b - a
		if d > 0 {
			heap.Push(&q, d)
			if q.Len() > ladders {
				bricks -= heap.Pop(&q).(int)
				if bricks < 0 {
					return i
				}
			}
		}
	}
	return n - 1
}

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 题解来源

1647. 字符频次唯一的最小删除次数

中等2 种解法

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

题目、示例与约束

如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。

给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。

字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。

 

示例 1：

输入：s = "aab"
输出：0
解释：s 已经是优质字符串。

示例 2：

输入：s = "aaabbbcc"
输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。

示例 3：

输入：s = "ceabaacb"
输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）

 

提示：

• 1 <= s.length <= 105
• s 仅含小写英文字母

方法一：数组 + 排序 · Go 实现

思考

要使各字母频次互异，只能删字符从而降低频次。字母种类只有 $26$，把频次从大到小排列后，每个值至多占用一个整数槽。

维护下一个仍可用的上限 $\mathit{\text{pre}}$：若当前频次 $v\ge \mathit{\text{pre}}$，必须删到 $\mathit{\text{pre}}-1$（若 $\mathit{\text{pre}}$ 已到 $0$ 则全部删掉）。

否则该频次可原样保留，并把 $\mathit{\text{pre}}$ 改成 $v$。

我们先用一个长度为 $26$ 的数组 $\mathit{\text{cnt}}$ 统计字符串 $s$ 中每个字母出现的次数。

然后我们对数组 $\mathit{\text{cnt}}$ 进行倒序排序。定义一个变量 $\mathit{\text{pre}}$ 记录当前字母的出现次数。

接下来，遍历数组 $\mathit{\text{cnt}}$ 每个元素 $v$，如果当前 $\mathit{\text{pre}}$ 等于 $0$，我们直接将答案加上 $v$；否则，如果 $v\ge \mathit{\text{pre}}$，我们将答案加上 $v-\mathit{\text{pre}}+1$，并且将 $\mathit{\text{pre}}$ 减去 $1$，否则，我们直接将 $\mathit{\text{pre}}$ 更新为 $v$。然后继续遍历下个元素。

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

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

func minDeletions(s string) (ans int) {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	sort.Sort(sort.Reverse(sort.IntSlice(cnt)))
	pre := 1 << 30
	for _, v := range cnt {
		if pre == 0 {
			ans += v
		} else if v >= pre {
			ans += v - pre + 1
			pre--
		} else {
			pre = v
		}
	}
	return
}

方法二：贪心（相邻递减） · Go 实现

思考

方法一用全局上限约束。等价地，排序后保证相邻频次严格递减：后者若不低于前者就一直减一，累计减少量即删除数。

实现更贴近「相邻互异」，复杂度同阶。

同样先统计并倒序排序出现次数。从前往后看相邻频次，若当前频次不小于前一个，就逐次减 $1$，直到严格更小。

时间复杂度 $O(n+|\mathrm{\Sigma }|\times \log |\mathrm{\Sigma }|+n)$，空间复杂度 $O(|\mathrm{\Sigma }|)$。其中 $n$ 是字符串 $s$ 的长度。

func minDeletions(s string) (ans int) {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	sort.Sort(sort.Reverse(sort.IntSlice(cnt)))
	for i := 1; i < 26; i++ {
		for cnt[i] >= cnt[i-1] && cnt[i] > 0 {
			cnt[i]--
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1648. 销售价值减少的颜色球

中等1 种解法

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

题目、示例与约束

你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。

这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）

给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。

请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 109 + 7 取余数 的结果。

 

示例 1：

输入：inventory = [2,5], orders = 4
输出：14
解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。
最大总和为 2 + 5 + 4 + 3 = 14 。

示例 2：

输入：inventory = [3,5], orders = 6
输出：19
解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。
最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。

示例 3：

输入：inventory = [2,8,4,10,6], orders = 20
输出：110

示例 4：

输入：inventory = [1000000000], orders = 1000000000
输出：21
解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 500000000500000000 对 109 + 7 取余为 21 。

 

提示：

• 1 <= inventory.length <= 105
• 1 <= inventory[i] <= 109
• 1 <= orders <= min(sum(inventory[i]), 109)

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

思考

每次应卖出当前库存最大的颜色。 $\mathit{\text{orders}}$ 可达 ${10}^9$，逐个卖会超时，需要按「同一最高库存的颜色个数」批量卖。

库存降序后，最高档与下一档的差值是一批，一批数量为档内颜色数乘以该差值；若超过剩余订单，再按等差数列求和拆成整轮与余数。

卖完一批后把最高库存降到下一档，继续直到订单耗尽，答案对 ${10}^9+7$ 取模。

要使得总价值最大，我们可以贪心地每次卖出数量最多的一种颜色的球。由于 orders 值域较大，如果直接简单地模拟，会超时。因此，我们需要优化模拟的过程。

实际上，我们不需要一次次进行模拟，我们可以跟踪数量最多的同色球的种类数 cnt，每一次可以卖出一批球，从而达到加速模拟的目的。

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

func maxProfit(inventory []int, orders int) int {
	var mod int = 1e9 + 7
	i, n, ans := 0, len(inventory), 0
	sort.Ints(inventory)
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		inventory[i], inventory[j] = inventory[j], inventory[i]
	}
	for orders > 0 {
		for i < n && inventory[i] >= inventory[0] {
			i++
		}
		nxt := 0
		if i < n {
			nxt = inventory[i]
		}
		cnt := i
		x := inventory[0] - nxt
		tot := cnt * x
		if tot > orders {
			decr := orders / cnt
			a1, an := inventory[0]-decr+1, inventory[0]
			ans += (a1 + an) * decr / 2 * cnt
			ans += (a1 - 1) * (orders % cnt)
		} else {
			a1, an := nxt+1, inventory[0]
			ans += (a1 + an) * x / 2 * cnt
			inventory[0] = nxt
		}
		orders -= tot
		ans %= mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

1663. 具有给定数值的最小字符串

中等1 种解法

标签：贪心、字符串

题目、示例与约束

小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

• x 是 y 的一个前缀；
• 如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

 

示例 1：

输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

示例 2：

输入：n = 5, k = 73
输出："aaszz"

 

提示：

• 1 <= n <= 105
• n <= k <= 26 * n

方法一：贪心 · Go 实现

思考

长度为 $n$、数值和为 $k$ 的字典序最小串，应尽量让左边是 a、把大字母堆到右侧。 $n$ 达 ${10}^5$，从右往左贪心填 z。

先全部放 a，剩余 $d=k-n$；从末尾只要 $d>25$ 就改成 z 并减 $25$，最后把余数加到当前位。

我们先将字符串的每个字符都初始化为 'a'，此时剩余的数值为 $d=k-n$。

接着从后往前遍历字符串，每次贪心地将当前位置的字符替换为能够使得剩余的数字最小的字符 'z'，直到剩余的数字不超过 $25$。最后将剩余的数字加到我们遍历到的位置上即可。

时间复杂度 $O(n)$，其中 $n$ 为字符串的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

func getSmallestString(n int, k int) string {
	ans := make([]byte, n)
	for i := range ans {
		ans[i] = 'a'
	}
	i, d := n-1, k-n
	for ; d > 25; i, d = i-1, d-25 {
		ans[i] = 'z'
	}
	ans[i] += byte(d)
	return string(ans)
}

力扣原题 · Doocs 题解来源

1665. 完成所有任务的最少初始能量

困难1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

• actuali 是完成第 i 个任务 需要耗费 的实际能量。
• minimumi 是开始第 i 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

 

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

 

提示：

• 1 <= tasks.length <= 105
• 1 <= actual​i <= minimumi <= 104

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

思考

每项任务有实际消耗 $a_i$ 与门槛 $m_i$，顺序可任选，求最小初始能量。 $n$ 达 ${10}^5$，应确定最优次序再一次扫描。

完成最后一项时， $E-\sum _{i<n}{a}_i\ge m_n$，整理后发现应让最后一项的 $m-a$ 尽量小，即按 $a-m$ 升序排列。

排序后若当前能量不足门槛则补齐，再减去 $a$，累计补齐量即答案。

我们假设任务数为 $n$，初始能量值为 $E$，考虑完成最后一个任务，这需要我们完成前 $n-1$ 个任务后，剩余的能量值不小于完成最后一个任务需要达到的能量值 $m_n$，即：

$$E-\sum _{i=1}^{n-1}{a}_i\ge m_n$$

我们可以将 $m_n$ 表示成 $a_n+(m_n-a_n)$，然后将上面的式子变形，得到：

$$E-\sum _{i=1}^{n-1}{a}_i\ge a_n+(m_n-a_n)$$

整理可得：

$$E\ge \sum _{i=1}^n{a}_i+(m_n-a_n)$$

其中 $\sum _{i=1}^n{a}_i$ 是固定不变的，要使得初始值能量值 $E$ 最小，我们需要让 $m_n-a_n$ 最小，即 $a_n-m_n$ 最大。

因此，我们可以将任务按照 $a_i-m_i$ 从小到大排序。然后从前往后遍历任务，对于每个任务，如果当前能量值 $cur$ 小于 $m_i$，则需要增加能量值 $m_i-cur$，使得当前能量值刚好等于 $m_i$，然后再完成任务，更新 $cur=cur-a_i$。继续遍历，直到完成所有任务，即可得到初始所需的最少能量值。

时间复杂度 $O(n\times \log n)$。其中 $n$ 为任务数。忽略排序的空间开销，空间复杂度 $O(1)$。

func minimumEffort(tasks [][]int) (ans int) {
	sort.Slice(tasks, func(i, j int) bool { return tasks[i][0]-tasks[i][1] < tasks[j][0]-tasks[j][1] })
	cur := 0
	for _, task := range tasks {
		a, m := task[0], task[1]
		if cur < m {
			ans += m - cur
			cur = m
		}
		cur -= a
	}
	return
}

力扣原题 · Doocs 题解来源

1673. 找出最具竞争力的子序列

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。

 

示例 1：

输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

示例 2：

输入：nums = [2,4,3,3,5,4,9,6], k = 4
输出：[2,3,3,4]

 

提示：

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

方法一：栈 · Go 实现

思考

长度为 $k$ 的最有竞争力子序列即字典序最小的长度为 $k$ 的子序列。 $n$ 达 ${10}^5$，用单调栈：栈顶更大且后面还够凑满 $k$ 个就弹出。

栈长不足 $k$ 时压入当前值，扫完栈中即答案。

我们从左到右遍历数组 nums，维护一个栈 stk，遍历过程中，如果当前元素 nums[i] 小于栈顶元素，且栈中元素个数加上 $n-i$ 大于 $k$，则将栈顶元素出栈，直到不满足上述条件为止。此时如果栈中元素个数小于 $k$，则将当前元素入栈。

遍历结束后，栈中元素即为所求。

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

func mostCompetitive(nums []int, k int) []int {
	stk := []int{}
	n := len(nums)
	for i, v := range nums {
		for len(stk) > 0 && stk[len(stk)-1] > v && len(stk)+n-i > k {
			stk = stk[:len(stk)-1]
		}
		if len(stk) < k {
			stk = append(stk, v)
		}
	}
	return stk
}

力扣原题 · Doocs 题解来源

1675. 数组的最小偏移量

困难1 种解法

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

题目、示例与约束

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

你可以对数组的任意元素执行任意次数的两类操作：

• 如果元素是 偶数 ，除以 2
  • 例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
• 如果元素是 奇数 ，乘上 2
  • 例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

 

示例 1：

输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1

示例 2：

输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3

示例 3：

输入：nums = [2,10,8]
输出：3

 

提示：

• n == nums.length
• 2 <= n <= 5 * 104
• 1 <= nums[i] <= 109

方法一：贪心 + 优先队列 · Go 实现

思考

奇数只能乘 $2$ 一次，偶数可反复除 $2$，目标是最小化 $max-min$。 $n$ 达 $5\times {10}^4$，需要避免对每个数枚举所有可达值。

先把奇数一律乘 $2$，此后只需对当前最大值除 $2$。大根堆维护最大值，并跟踪全局最小；每次把堆顶折半放回并更新偏差，直到堆顶变为奇数无法再缩小。

直观上，为了得到数组的最小偏移量，我们需要将减小数组的最大值，增大数组的最小值。

由于每次可以执行乘、除两种操作：将奇数乘以 $2$；将偶数除以 $2$，情况较为复杂，我们可以将奇数统一乘以 $2$，转成偶数，这样就等价于只有一种除法操作。除法操作只能减少某个数，而只有减少最大值，结果才可能更优。

因此，我们用优先队列（大根堆）维护数组的最大值，每次取出堆顶元素做除法操作，将新值放入堆中，并且更新最小值以及堆顶元素与最小值的差值的最小值。

当堆顶元素为奇数时，操作停止。

时间复杂度 $O(n\log n\times \log m)$。其中 $n$, $m$ 分别是数组 nums 的长度以及数组的最大元素。由于数组中的最大元素除以 $2$ 的操作最多有 $O(\log m)$ 次，因此全部元素除以 $2$ 的操作最多有 $O(n\log m)$ 次。每次弹出、放入堆的操作，时间复杂度为 $O(\log n)$。因此，总的时间复杂度为 $O(n\log n\times \log m)$。

func minimumDeviation(nums []int) int {
	q := hp{}
	mi := math.MaxInt32
	for _, v := range nums {
		if v%2 == 1 {
			v <<= 1
		}
		heap.Push(&q, v)
		mi = min(mi, v)
	}
	ans := q.IntSlice[0] - mi
	for q.IntSlice[0]%2 == 0 {
		x := heap.Pop(&q).(int) >> 1
		heap.Push(&q, x)
		mi = min(mi, x)
		ans = min(ans, q.IntSlice[0]-mi)
	}
	return ans
}

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 题解来源

1686. 石子游戏 VI

中等1 种解法

标签：贪心、极小化极大、数组、数学、博弈、排序、堆（优先队列）、零和博弈

题目、示例与约束

Alice 和 Bob 轮流玩一个游戏，Alice 先手。

一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果，用如下的方式表示：

• 如果 Alice 赢，返回 1 。
• 如果 Bob 赢，返回 -1 。
• 如果游戏平局，返回 0 。

 

示例 1：

输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。

示例 2：

输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。

示例 3：

输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

 

提示：

• n == aliceValues.length == bobValues.length
• 1 <= n <= 105
• 1 <= aliceValues[i], bobValues[i] <= 100

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

思考

双方轮流取石，取走一枚自己得分、对手失去对应分数。比较价值时应同时考虑「自己得到 $a_i$」与「不让对手得到 $b_i$」，即按 $a_i+b_i$ 降序轮流拿。

排序后 Alice 取偶数位、Bob 取奇数位，比较两人得分给出 $1$、 $0$ 或 $-1$。

选取石头的最优化的策略是，让自己得分最高，同时让对手失分最多。因此，我们创建一个数组 $vals$，其中 $vals[i]=(aliceValues[i]+bobValues[i],i)$，表示第 $i$ 个石头的总价值和编号。然后我们对 $vals$ 按照总价值降序排序。

然后我们按照 $vals$ 的顺序，让 Alice 和 Bob 交替选取石头。Alice 选取 $vals$ 中的偶数位置的石头，Bob 选取 $vals$ 中的奇数位置的石头。最后比较 Alice 和 Bob 的得分，返回对应的结果。

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

func stoneGameVI(aliceValues []int, bobValues []int) int {
	vals := make([][2]int, len(aliceValues))
	for i, a := range aliceValues {
		vals[i] = [2]int{a + bobValues[i], i}
	}
	slices.SortFunc(vals, func(a, b [2]int) int { return b[0] - a[0] })
	a, b := 0, 0
	for k, v := range vals {
		i := v[1]
		if k%2 == 0 {
			a += aliceValues[i]
		} else {
			b += bobValues[i]
		}
	}
	if a > b {
		return 1
	}
	if a < b {
		return -1
	}
	return 0
}

力扣原题 · Doocs 题解来源

1689. 十-二进制数的最少数目

中等1 种解法

标签：贪心、字符串

题目、示例与约束

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

 

示例 1：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32

示例 2：

输入：n = "82734"
输出：8

示例 3：

输入：n = "27346209830709182346"
输出：9

 

提示：

• 1 <= n.length <= 105
• n 仅由数字组成
• n 不含任何前导零并总是表示正整数

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

思考

十进制二进制数每位只能是 $0$ 或 $1$，把它们相加得到 $n$ 时，某一位为 $d$ 至少需要 $d$ 个数在该位为 $1$。因此答案就是 $n$ 各位数字的最大值。

题目等价于找字符串中的最大数。

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

func minPartitions(n string) (ans int) {
	for _, c := range n {
		ans = max(ans, int(c-'0'))
	}
	return
}

力扣原题 · Doocs 题解来源