LeetCode Go · 贪心（5）

来源与许可

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

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

1702. 修改后的最大二进制字符串

中等1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。
- 比方说， "00010" -> "10010"
操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。
- 比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1：

输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2：

输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。

提示：

1 <= binary.length <= 10⁵
binary 仅包含 '0' 和 '1' 。

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

思考

操作允许把 $00$ 换成 $10$ 、把 $10$ 换成 $01$ 。若对每一次替换做搜索，状态空间随串长指数增长，难以在约束内完成。

操作 $2$ 可将任意 $1$ 向右挪动，操作 $1$ 则把连续 $0$ 压成「若干 $1$ 后接一个 $0$ 」。因此最优形态至多含一个 $0$ ，且该 $0$ 应尽量靠右。

第一个 $0$ 之前的前缀 $1$ 无法被改动；其后所有 $0$ 可汇聚到同一位置。设首个 $0$ 的下标为 $k$ ，再加上其后 $0$ 的个数，即得最终 $0$ 的下标，其余位填 $1$ 。

我们观察发现，操作 $2$ 可以把所有的 $1$ 都移动到字符串的末尾，而操作 $1$ 可以把所有的 0000..000 串变为 111..110。

因此，要想得到最大的二进制串，我们应该把所有不在开头的 $1$ 移动到字符串末尾，使得字符串变为 111..11...000..00..11 的形式，然后借助操作 $1$ 把中间的 000..00 变为 111..10。这样我们最终可以得到一个最多包含一个 $0$ 的二进制字符串，这个字符串就是我们要求的最大二进制串。

在代码实现上，我们首先判断字符串是否包含 $0$ ，如果不包含，直接返回原字符串。否则，我们找到第一个 $0$ 的位置 $k$ ，加上该位置之后的 $0$ 的个数，得到的就是修改后的字符串的 $0$ 所在的位置，其余位置都是 $1$ 。

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

func maximumBinaryString(binary string) string {
	k := strings.IndexByte(binary, '0')
	if k == -1 {
		return binary
	}
	for _, c := range binary[k+1:] {
		if c == '0' {
			k++
		}
	}
	ans := []byte(binary)
	for i := range ans {
		ans[i] = '1'
	}
	ans[k] = '0'
	return string(ans)
}

力扣原题 · Doocs 题解来源

1703. 得到连续 K 个 1 的最少相邻交换次数

困难1 种解法

标签：贪心、数组、前缀和、滑动窗口

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择相邻两个数字并将它们交换。

请你返回使 nums 中包含 k 个连续 1 的最少交换次数。

示例 1：

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

示例 2：

输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。

示例 3：

输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。

提示：

1 <= nums.length <= 10⁵
nums[i] 要么是 0 ，要么是 1 。
1 <= k <= sum(nums)

方法一：前缀和 + 中位数枚举 · Go 实现

思考

相邻交换把 $k$ 个 $1$ 聚到连续区间，等价于把这些 $1$ 的下标搬到长度为 $k$ 的目标区间。若对每个窗口枚举目标位置，复杂度过高， $n \leq 10^{5}$ 需要线性或近似线性做法。

一次相邻交换只改变下标差 $1$ ，因此总交换次数等于各 $1$ 下标到目标位置的距离之和。该和在目标取这 $k$ 个下标的中位数时最小。

将 $1$ 的下标记入 $a r r$ 并做前缀和。枚举窗口中位数 $a r r [i]$ ，用前缀和在 $O (1)$ 内算出左右两侧收到中位数邻域的代价，取最小值。

我们可以将数组 $n u m s$ 中的 $1$ 的下标存入数组 $a r r$ 中。接下来，我们预处理数组 $a r r$ 的前缀和数组 $s$ ，其中 $s [i]$ 表示数组 $a r r$ 中前 $i$ 个元素的和。

对于长度为 $k$ 的子数组，左侧（包含中位数）的元素个数 $x = \frac{k + 1}{2}$ ，右侧的元素个数为 $y = k - x$ 。

我们枚举中位数的下标 $i$ ，其中 $x - 1 \leq i \leq l e n (a r r) - y$ ，那么左侧数组的前缀和 $l s = s [i + 1] - s [i + 1 - x]$ ，右侧数组的前缀和 $r s = s [i + 1 + y] - s [i + 1]$ 。当前中位数在 $n u m s$ 中的下标为 $j = a r r [i]$ ，将左侧 $x$ 个元素移动到 $[j - x + 1, . . j]$ 所需要的操作次数为 $a = (j + j - x + 1) \times \frac{x}{2} - l s$ ，将右侧 $y$ 个元素移动到 $[j + 1, . . j + y]$ 所需要的操作次数为 $b = r s - (j + 1 + j + y) \times \frac{y}{2}$ ，那么总的操作次数为 $a + b$ ，我们取所有总的操作次数的最小值即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (m)$ 。其中 $n$ 和 $m$ 分别为数组 $n u m s$ 的长度以及数组 $n u m s$ 中 $1$ 的个数。

func minMoves(nums []int, k int) int {
	arr := []int{}
	for i, x := range nums {
		if x != 0 {
			arr = append(arr, i)
		}
	}
	s := make([]int, len(arr)+1)
	for i, x := range arr {
		s[i+1] = s[i] + x
	}
	ans := 1 << 60
	x := (k + 1) / 2
	y := k - x
	for i := x - 1; i < len(arr)-y; i++ {
		j := arr[i]
		ls := s[i+1] - s[i+1-x]
		rs := s[i+1+y] - s[i+1]
		a := (j+j-x+1)*x/2 - ls
		b := rs - (j+1+j+y)*y/2
		ans = min(ans, a+b)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1705. 吃苹果的最大数目

中等1 种解法

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

题目、示例与约束

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天最多吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

示例 1：

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

示例 2：

输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出：5
解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。

提示：

apples.length == n
days.length == n
1 <= n <= 2 * 10⁴
0 <= apples[i], days[i] <= 2 * 10⁴
只有在 apples[i] = 0 时，days[i] = 0 才成立

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

思考

每天至多吃一个苹果，且必须吃尚未腐烂的。若随意选择，容易先吃掉保质期长的而浪费即将过期的，最终吃到的个数偏少。

在仍可食用的苹果中优先吃最早腐烂的，才能在每一天尽量不浪费。这对应按腐烂日期维护小根堆。

第 $i$ 天若有新苹果则把 $(腐烂日, 数量)$ 入堆；弹出已过期的批次后，取堆顶吃一颗并写回剩余。持续到既无新货也无库存。

我们可以贪心地在未腐烂的苹果中优先选择最容易腐烂的苹果，这样可以使得吃到的苹果尽可能多。

因此，我们可以用优先队列（小根堆）存储苹果的腐烂时间以及对应苹果的数量，每次从优先队列中取出腐烂时间最小的苹果，然后将其数量减一，若减一后苹果的数量不为零，则将其重新放入优先队列中。若苹果已经腐烂，则从优先队列中弹出。

时间复杂度 $O (n \times \log n + M)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $days$ 的长度，而 $M = max (days)$ 。

func eatenApples(apples []int, days []int) int {
	var h hp
	ans, n := 0, len(apples)
	for i := 0; i < n || len(h) > 0; i++ {
		if i < n && apples[i] > 0 {
			heap.Push(&h, pair{i + days[i] - 1, apples[i]})
		}
		for len(h) > 0 && h[0].first < i {
			heap.Pop(&h)
		}
		if len(h) > 0 {
			h[0].second--
			if h[0].first == i || h[0].second == 0 {
				heap.Pop(&h)
			}
			ans++
		}
	}
	return ans
}

type pair struct {
	first  int
	second 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].first < a[j].first }
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 }

力扣原题 · Doocs 题解来源

1708. 长度为 K 的最大子数组 🔒

简单1 种解法

标签：贪心、数组

题目、示例与约束

在数组 A 和数组 B 中，对于第一个满足 A[i] != B[i] 的索引 i ，当 A[i] > B[i] 时，数组 A 大于数组 B。

例如，对于索引从 0 开始的数组：

[1,3,2,4] > [1,2,2,4] ，因为在索引 1 上， 3 > 2。
[1,4,4,4] < [2,1,1,1] ，因为在索引 0 上， 1 < 2。

一个数组的子数组是原数组上的一个连续子序列。

给定一个包含不同整数的整数类型数组 nums ，返回 nums 中长度为 k 的最大子数组。

示例 1:

输入: nums = [1,4,5,2,3], k = 3
输出: [5,2,3]
解释: 长度为 3 的子数组有： [1,4,5]、 [4,5,2] 和 [5,2,3]。
在这些数组中， [5,2,3] 是最大的。

示例 2:

输入: nums = [1,4,5,2,3], k = 4
输出: [4,5,2,3]
解释: 长度为 4 的子数组有： [1,4,5,2] 和 [4,5,2,3]。
在这些数组中， [4,5,2,3] 是最大的。

示例 3:

输入: nums = [1,4,5,2,3], k = 1
输出: [5]

提示：

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
nums 中的所有整数都是不同的。

进阶：如果允许 nums 中存在相同元素，你该如何解决该问题？

方法一：模拟 · Go 实现

思考

长度为 $k$ 的子数组中，字典序最大者由其第一个元素决定，因为数组元素互不相同。

合法起点落在 $[0, n - k]$ 。在该区间取最大值的下标 $i$ ，子数组即为 $n u m s [i . . i + k)$ 。一次遍历即可。

数组中所有整数都不同，我们可以先在 $[0, . . n - k]$ 范围内找到最大的元素的下标，然后从该下标开始取 $k$ 个元素即可。

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

func largestSubarray(nums []int, k int) []int {
	j := 0
	for i := 1; i < len(nums)-k+1; i++ {
		if nums[j] < nums[i] {
			j = i
		}
	}
	return nums[j : j+k]
}

力扣原题 · Doocs 题解来源

1710. 卡车上的最大单元数

简单2 种解法

标签：贪心、数组、排序

题目、示例与约束

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i] ：

numberOfBoxes_i 是类型 i 的箱子的数量。
numberOfUnitsPerBox_i是类型 i 每个箱子可以装载的单元数量。

整数 truckSize 表示卡车上可以装载箱子的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。

返回卡车可以装载单元的最大总数。

示例 1：

输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8

示例 2：

输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91

提示：

1 <= boxTypes.length <= 1000
1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10⁶

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

思考

卡车容量按箱计数，而目标是单元数最大。同类箱单元数相同，应优先装单元密度高的箱子。

按每箱单元数降序排序后，依次装入 $min (truckSize, 箱数)$ 个，更新剩余容量，容量耗尽即停。

根据题意，我们应该选择尽可能多的单元数，因此，我们先对 boxTypes 按照单元数从大到小的顺序排列。

然后从前往后遍历 boxTypes，选择最多 truckSize 个箱子，累加单元数。

时间复杂度 $O (n \times \log n)$ ，其中 $n$ 表示二维数组 boxTypes 的长度。

func maximumUnits(boxTypes [][]int, truckSize int) (ans int) {
	sort.Slice(boxTypes, func(i, j int) bool { return boxTypes[i][1] > boxTypes[j][1] })
	for _, e := range boxTypes {
		a, b := e[0], e[1]
		ans += b * min(truckSize, a)
		truckSize -= a
		if truckSize <= 0 {
			break
		}
	}
	return
}

方法二：计数排序 · Go 实现

思考

方法一的排序代价为 $O (n \log n)$ 。每箱单元数不超过 $1000$ ，可用计数数组按值下标存放箱数。

从 $1000$ 扫到 $1$ ，按单元数从大到小装车，线性完成同一贪心。

我们还可以利用计数排序的思想，开一个长度为 $1001$ 的数组 $c n t$ ，其中 $c n t [b]$ 表示单元数为 $b$ 的箱子的数量。

然后从单元数最大的箱子开始，选择最多 truckSize 个箱子，累加单元数。

时间复杂度 $O (M)$ ，其中 $M$ 是单元数的最大值。本题中 $M = 1000$ 。

func maximumUnits(boxTypes [][]int, truckSize int) (ans int) {
	cnt := [1001]int{}
	for _, e := range boxTypes {
		a, b := e[0], e[1]
		cnt[b] += a
	}
	for b := 1000; b > 0 && truckSize > 0; b-- {
		a := cnt[b]
		if a > 0 {
			ans += b * min(truckSize, a)
			truckSize -= a
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1713. 得到子序列的最少操作次数

困难1 种解法

标签：贪心、数组、哈希表、二分查找、最长上升子序列

题目、示例与约束

给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能包含重复元素。

每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。

请你返回最少操作次数，使得 target 成为 arr 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。

示例 1：

输入：target = [5,1,3], arr = [9,4,2,3,4]
输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。

示例 2：

输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出：3

提示：

1 <= target.length, arr.length <= 10⁵
1 <= target[i], arr[i] <= 10⁹
target 不包含任何重复元素。

方法一：最长递增子序列 + 树状数组 · Go 实现

思考

最少插入次数等于 $| target |$ 减去最长公共子序列长度。标准 LCS 为 $O (m n)$ ，两边长度均达 $10^{5}$ ，不可行。

$target$ 元素互异，因此 $a r r$ 中出现在 $target$ 里的值可映射为 $target$ 下标。LCS 退化为该下标序列的最长递增子序列。

用树状数组维护「小于当前下标的最大 LIS」，每次查询 $x - 1$ 再更新 $x$ 。答案为 $m$ 减去 LIS 长度。

根据题意，target 和 arr 这两个数组的公共子序列越长，需要添加的元素就越少。因此，最少添加的元素个数等于 target 的长度减去 target 和 arr 的最长公共子序列的长度。

但是，求最长公共子序列的时间复杂度为 $O (m \times n)$ ，无法通过本题，需要转变思路。

我们可以用一个哈希表记录 target 数组中每个元素的下标，然后遍历 arr 数组，对于 arr 数组中的每个元素，如果哈希表中存在该元素，则将该元素的下标加入到一个数组中，这样就得到了一个新的数组 nums，该数组是 arr 中的元素在 target 数组中的下标（去掉了不在 target 中的元素），该数组的最长递增子序列的长度就是 target 和 arr 的最长公共子序列的长度。

因此，问题转化为求 nums 数组的最长递增子序列的长度。参考 300. 最长递增子序列。

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

type BinaryIndexedTree struct {
	n int
	c []int
}

func NewBinaryIndexedTree(n int) BinaryIndexedTree {
	return BinaryIndexedTree{n: n, c: make([]int, n+1)}
}

func (bit *BinaryIndexedTree) Update(x, v int) {
	for ; x <= bit.n; x += x & -x {
		if v > bit.c[x] {
			bit.c[x] = v
		}
	}
}

func (bit *BinaryIndexedTree) Query(x int) int {
	ans := 0
	for ; x > 0; x -= x & -x {
		if bit.c[x] > ans {
			ans = bit.c[x]
		}
	}
	return ans
}

func minOperations(target []int, arr []int) int {
	m := len(target)
	d := make(map[int]int)
	for i, x := range target {
		d[x] = i + 1
	}
	var nums []int
	for _, x := range arr {
		if pos, exists := d[x]; exists {
			nums = append(nums, pos)
		}
	}
	tree := NewBinaryIndexedTree(m)
	ans := 0
	for _, x := range nums {
		v := tree.Query(x-1) + 1
		if v > ans {
			ans = v
		}
		tree.Update(x, v)
	}
	return m - ans
}

力扣原题 · Doocs 题解来源

1717. 删除子字符串的最大得分

中等1 种解法

标签：栈、贪心、字符串

题目、示例与约束

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

删除子字符串 "ab" 并得到 x 分。
- 比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
删除子字符串"ba" 并得到 y 分。
- 比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20

提示：

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s 只包含小写英文字母。

方法一：贪心 · Go 实现

思考

每次删除 $ab$ 得 $x$ 、删除 $ba$ 得 $y$ ，删除会改变邻接。搜索所有删除顺序在长串上不可行。

一段仅含 $a, b$ 的子串无论怎么删，最终只剩一种字符，操作次数由两种字母的个数决定。应先删分值更高的模式。

若 $x < y$ 则交换字母与分值。扫描时优先用计数匹配高分对；遇到其它字符或结束时，再用 $min (c n t_{a}, c n t_{b})$ 结算低分对。

我们不妨假设子字符串 "ab" 的得分总是不低于子字符串 "ba" 的得分，如果不是，我们可以交换 "a" 和 "b"，同时交换 $x$ 和 $y$ 。

接下来，我们只需要考虑字符串中只包含 "a" 和 "b" 的情况。如果字符串中包含其他字符，我们可以将其视为一个分割点，将字符串分割成若干个只包含 "a" 和 "b" 的子字符串，然后分别计算每个子字符串的得分。

我们观察发现，对于一个只包含 "a" 和 "b" 的子字符串，无论采取什么样的操作，最后一定只剩下一种字符，或者空串。由于每次操作都会同时删除一个 "a" 和一个 "b"，因此总的操作次数一定是固定的。我们可以贪心地先删除 "ab"，再删除 "ba"，这样可以保证得分最大。

因此，我们可以使用两个变量 $cnt1$ 和 $cnt2$ 分别记录 "a" 和 "b" 的数量，然后遍历字符串，根据当前字符的不同情况更新 $cnt1$ 和 $cnt2$ ，并计算得分。

对于当前遍历到的字符 $c$ ：

如果 $c$ 是 "a"，由于要先删除 "ab"，因此此时我们不消除该字符，只增加 $cnt1$ ；
如果 $c$ 是 "b"，如果此时 $cnt1 > 0$ ，我们可以消除一个 "ab"，并增加 $x$ 分，否则我们只能增加 $cnt2$ ；
如果 $c$ 是其他字符，那么对于该子字符串，我们剩下了 $cnt2$ 个 "b" 和 $cnt1$ 个 "a"，我们可以消除 $min (cnt1, cnt2)$ 个 "ba"，并增加若干个 $y$ 分。

遍历结束后，我们还需要额外处理一下剩余的 "ba"，增加若干个 $y$ 分。

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

func maximumGain(s string, x int, y int) (ans int) {
	a, b := 'a', 'b'
	if x < y {
		x, y = y, x
		a, b = b, a
	}

	var cnt1, cnt2 int
	for _, c := range s {
		if c == a {
			cnt1++
		} else if c == b {
			if cnt1 > 0 {
				ans += x
				cnt1--
			} else {
				cnt2++
			}
		} else {
			ans += min(cnt1, cnt2) * y
			cnt1, cnt2 = 0, 0
		}
	}
	ans += min(cnt1, cnt2) * y
	return
}

力扣原题 · Doocs 题解来源

1727. 重新排列后的最大子矩阵

中等1 种解法

标签：贪心、数组、矩阵、排序

题目、示例与约束

给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的列按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后，全是 1 的最大子矩阵面积。

示例 1：

输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。

示例 2：

输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。

示例 3：

输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。

示例 4：

输入：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。

提示：

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] 要么是 0 ，要么是 1 。

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

思考

列可任意重排，求全 $1$ 子矩阵的最大面积。 $m \cdot n \leq 10^{5}$ ，不能对每种排列枚举。

重排只改列序，不改一列里向上连续 $1$ 的高度。把每个 $1$ 改写成向上高度后，同一行的高度可当作柱状图。

每行降序排序，第 $k$ 大高度 $v$ 可与前 $k$ 列组成高为 $v$ 的全 $1$ 矩阵，面积 $k \cdot v$ 。对所有行取最大。

由于题目中矩阵是按列进行重排，因此，我们可以先对矩阵的每一列进行预处理。

对于每个值为 $1$ 的元素，我们更新其值为该元素向上的最大连续的 $1$ 的个数，即 $matrix [i] [j] = matrix [i - 1] [j] + 1$ 。

接下来，我们可以对更新后的矩阵的每一行进行排序。然后遍历每一行，计算以该行作为底边的最大全 $1$ 子矩阵的面积。具体计算逻辑如下：

对于矩阵的某一行，我们记第 $k$ 大元素的值为 ${val}_{k}$ ，其中 $k \geq 1$ ，那么该行至少有 $k$ 个元素不小于 ${val}_{k}$ ，组成的全 $1$ 子矩阵面积为 ${val}_{k} \times k$ 。从大到小遍历矩阵该行的每个元素，取 ${val}_{k} \times k$ 的最大值，更新答案。

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

func largestSubmatrix(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	for i := 1; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 1 {
				matrix[i][j] = matrix[i-1][j] + 1
			}
		}
	}
	ans := 0
	for _, row := range matrix {
		sort.Ints(row)
		for j, k := n-1, 1; j >= 0 && row[j] > 0; j, k = j-1, k+1 {
			ans = max(ans, row[j]*k)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1733. 需要教语言的最少人数

中等1 种解法

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

题目、示例与约束

在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。

给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：

总共有 n 种语言，编号从 1 到 n 。
languages[i] 是第 i 位用户掌握的语言集合。
friendships[i] = [u_i, v_i] 表示 u_i 和 v_i 为好友关系。

你可以选择一门语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你最少需要教会多少名用户。

请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。

示例 1：

输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出：1
解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。

示例 2：

输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2
解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。

提示：

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
所有的好友关系 (u_i,v_i) 都是唯一的。
languages[i] 中包含的值互不相同。

方法一：模拟 + 统计 · Go 实现

思考

只能教一种语言，且只需让当前不能沟通的好友对变得能沟通。好友关系无跨对传递，不必考虑间接连通。

先收集所有「语言集合不相交」的好友两端，这些人构成必须被考虑的集合 $s$ 。

在 $s$ 中统计各语言的掌握人数，教掌握最多的那种，需教人数为 $| s |$ 减去该最大值。

对于每个好友关系，如果两个人掌握的语言集合不相交，则需要教一门语言，使得两个人可以相互沟通，我们将这些人放入一个哈希集合 $s$ 中。

然后在这个集合 $s$ 中，统计每种语言掌握的人数，获取最大的人数，我们记为 $m x$ ，那么答案就是 $| s | - m x$ 。其中 $| s |$ 表示集合 $s$ 的大小。

时间复杂度 $O (m^{2} \times k)$ 。其中 $m$ 为语言的数量，而 $k$ 为好友关系的数量。

func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
	check := func(u, v int) bool {
		for _, x := range languages[u-1] {
			for _, y := range languages[v-1] {
				if x == y {
					return true
				}
			}
		}
		return false
	}
	s := map[int]bool{}
	for _, e := range friendships {
		u, v := e[0], e[1]
		if !check(u, v) {
			s[u], s[v] = true, true
		}
	}
	if len(s) == 0 {
		return 0
	}
	cnt := make([]int, n+1)
	for u := range s {
		for _, l := range languages[u-1] {
			cnt[l]++
		}
	}
	return len(s) - slices.Max(cnt)
}

力扣原题 · Doocs 题解来源

1736. 替换隐藏数字得到的最晚时间

简单1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。

有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。

替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。

示例 1：

输入：time = "2?:?0"
输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。

示例 2：

输入：time = "0?:3?"
输出："09:39"

示例 3：

输入：time = "1?:22"
输出："19:22"

提示：

time 的格式为 hh:mm
题目数据保证你可以由输入的字符串生成有效的时间

方法一：贪心 · Go 实现

思考

合法时刻为 $00$ : $00$ 到 $23$ : $59$ ，要把 $?$ 换成数字使时刻尽量晚。各位约束局部，从左到右贪心取最大可行数字即可。

小时十位依赖个位是否已是 $4$ – $9$ ；小时个位依赖十位是否为 $2$ ；分钟两位分别最大为 $5$ 与 $9$ 。

我们依次处理字符串的每一位，处理的规则如下：

第一位：若第二位的值已确定，且值落在区间 $[4, 9]$ 内，那么第一位只能取 $1$ ，否则第一位最大取 $2$ ；
第二位：若第一位的值已确定，且值为 $2$ ，那么第二位最大取 $3$ ，否则第二位最大取 $9$ ；
第三位：第三位最大取 $5$ ；
第四位：第四位最大取 $9$ 。

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

func maximumTime(time string) string {
	t := []byte(time)
	if t[0] == '?' {
		if t[1] >= '4' && t[1] <= '9' {
			t[0] = '1'
		} else {
			t[0] = '2'
		}
	}
	if t[1] == '?' {
		if t[0] == '2' {
			t[1] = '3'
		} else {
			t[1] = '9'
		}
	}
	if t[3] == '?' {
		t[3] = '5'
	}
	if t[4] == '?' {
		t[4] = '9'
	}
	return string(t)
}

力扣原题 · Doocs 题解来源

1739. 放置盒子

困难1 种解法

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

题目、示例与约束

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：

你可以把盒子放在地板上的任何地方。
如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都必须与另一个盒子或墙相邻。

给你一个整数 n ，返回接触地面的盒子的最少可能数量。

示例 1：

输入：n = 3
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。

示例 2：

输入：n = 4
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。

示例 3：

输入：n = 10
输出：6
解释：上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角，对应后方位置。

提示：

1 <= n <= 10⁹

方法一：数学规律 · Go 实现

思考

盒子堆在墙角呈阶梯，上层盒子要求下方四面被支撑。要使触地盒子尽量少，应先堆满尽可能高的正四面体状阶梯。

第 $k$ 层若摆满，个数为 $1 + \dots + k$ 。先累加完整层直到不能再加一整层，再在底层按 $1, 2, 3, \dots$ 补剩余盒子，每补一批触地数加一。

根据题目描述，层数最高的盒子需要放在墙角，并且盒子的摆放呈阶梯状，这样可以使得接触地面的盒子数量最少。

假设盒子摆放 $k$ 层，从上到下，每一层如果摆满，那么个数分别是 $1, 1 + 2, 1 + 2 + 3, \dots, 1 + 2 + \dots + k$ 。

如果此时盒子还有剩余，那么可以从最低一层继续摆放，假设摆放 $i$ 个，那么累计可摆放的盒子个数为 $1 + 2 + \dots + i$ 。

时间复杂度 $O (\sqrt{n})$ ，其中 $n$ 为题目给定的盒子数量。空间复杂度 $O (1)$ 。

func minimumBoxes(n int) int {
	s, k := 0, 1
	for s+k*(k+1)/2 <= n {
		s += k * (k + 1) / 2
		k++
	}
	k--
	ans := k * (k + 1) / 2
	k = 1
	for s < n {
		ans++
		s += k
		k++
	}
	return ans
}

力扣原题 · Doocs 题解来源

1753. 移除石子的最大得分

中等2 种解法

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

题目、示例与约束

你正在玩一个单人游戏，面前放置着大小分别为 a、b 和 c 的三堆石子。

每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 1 分。当存在 两个或更多 的空堆时，游戏停止。

给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。

示例 1：

输入：a = 2, b = 4, c = 6
输出：6
解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：
- 从第一和第三堆取，石子状态现在是 (1, 4, 5)
- 从第一和第三堆取，石子状态现在是 (0, 4, 4)
- 从第二和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：6 分 。

示例 2：

输入：a = 4, b = 4, c = 6
输出：7
解释：石子起始状态是 (4, 4, 6) ，最优的一组操作是：
- 从第一和第二堆取，石子状态现在是 (3, 3, 6)
- 从第一和第三堆取，石子状态现在是 (2, 3, 5)
- 从第一和第三堆取，石子状态现在是 (1, 3, 4)
- 从第一和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：7 分 。

示例 3：

输入：a = 1, b = 8, c = 8
输出：8
解释：最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。
注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。

提示：

1 <= a, b, c <= 10⁵

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

思考

每次从两堆非空堆各取一石。贪心总是削减当前最大的两堆，直到至少两堆为空。石子总数有限，模拟可行。

将三元组排序后反复减少后两堆并重新排序，计数即得分。

每次贪心地从最大的两堆石子中取石头，直到至少有两堆石子为空。

时间复杂度 $O (n)$ ，其中 $n$ 为石子总数。

func maximumScore(a int, b int, c int) (ans int) {
	s := []int{a, b, c}
	sort.Ints(s)
	for s[1] > 0 {
		ans++
		s[1]--
		s[2]--
		sort.Ints(s)
	}
	return
}

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

思考

方法一按步模拟。设 $a \leq b \leq c$ ：若 $a + b \leq c$ ，较小两堆都会先被耗尽，得分为 $a + b$ ；否则最终得分是 $⌊ (a + b + c) / 2 ⌋$ 。 $O (1)$ 求出。

我们不妨设 $a \leq b \leq c$ ，那么：

当 $a + b \leq c$ 时，我们可以先从 $a$ , $c$ 两堆中取石头，得到分数 $a$ ；再从 $b$ , $c$ 两堆中取石头，得到分数 $b$ ，总分数为 $a + b$ ；
当 $a + b > c$ 时，这时我们每次会从 $c$ 以及 $a$ 和 $b$ 中较大的那一堆中取石头，最终将 $c$ 取空。此时 $a$ 和 $b$ 的大小差最多为 $1$ 。我们再从 $a$ , $b$ 两堆中取石头，直到不能取为止，总分数为 $⌊ \frac{a + b + c}{2} ⌋$ 。

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

func maximumScore(a int, b int, c int) int {
	s := []int{a, b, c}
	sort.Ints(s)
	if s[0]+s[1] < s[2] {
		return s[0] + s[1]
	}
	return (a + b + c) >> 1
}

力扣原题 · Doocs 题解来源

1754. 构造字典序最大的合并字符串

中等1 种解法

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

题目、示例与约束

给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择 下面选项之一 继续操作：

如果 word1 非空，将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。
- 例如，word1 = "abc" 且 merge = "dv" ，在执行此选项操作之后，word1 = "bc" ，同时 merge = "dva" 。
如果 word2 非空，将 word2 中的第一个字符附加到 merge 的末尾，并将其从 word2 中移除。
- 例如，word2 = "abc" 且 merge = "" ，在执行此选项操作之后，word2 = "bc" ，同时 merge = "a" 。

返回你可以构造的字典序最大的合并字符串 merge 。

长度相同的两个字符串 a 和 b 比较字典序大小，如果在 a 和 b 出现不同的第一个位置，a 中字符在字母表中的出现顺序位于 b 中相应字符之后，就认为字符串 a 按字典序比字符串 b 更大。例如，"abcd" 按字典序比 "abcc" 更大，因为两个字符串出现不同的第一个位置是第四个字符，而 d 在字母表中的出现顺序位于 c 之后。

示例 1：

输入：word1 = "cabaa", word2 = "bcaaa"
输出："cbcabaaaaa"
解释：构造字典序最大的合并字符串，可行的一种方法如下所示：
- 从 word1 中取第一个字符：merge = "c"，word1 = "abaa"，word2 = "bcaaa"
- 从 word2 中取第一个字符：merge = "cb"，word1 = "abaa"，word2 = "caaa"
- 从 word2 中取第一个字符：merge = "cbc"，word1 = "abaa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbca"，word1 = "baa"，word2 = "aaa"
- 从 word1 中取第一个字符：merge = "cbcab"，word1 = "aa"，word2 = "aaa"
- 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。

示例 2：

输入：word1 = "abcabc", word2 = "abdcaba"
输出："abdcabcabcaba"

提示：

1 <= word1.length, word2.length <= 3000
word1 和 word2 仅由小写英文组成

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

思考

每次只能取某个串的首字符。字典序最大意味着当前应取「剩余串」更大的那一侧的首字符，而不是只比较单个字符。

双指针比较 $w o r d 1 [i :]$ 与 $w o r d 2 [j :]$ ，取较大者的首字符，直到一侧耗尽再拼接剩余。

我们用指针 $i$ 和 $j$ 分别指向字符串 word1 和 word2 的第一个字符。然后循环，每次比较 $w o r d 1 [i :]$ 和 $w o r d 2 [j :]$ 的大小，如果 $w o r d 1 [i :]$ 比 $w o r d 2 [j :]$ 大，那么我们就将 $w o r d 1 [i]$ 加入答案，否则我们就将 $w o r d 2 [j]$ 加入答案。循环，直至 $i$ 到达字符串 word1 的末尾，或者 $j$ 到达字符串 word2 的末尾。

然后我们将剩余的字符串加入答案即可。

时间复杂度 $O (n^{2})$ 。其中 $n$ 是字符串 word1 和 word2 的长度之和。

func largestMerge(word1 string, word2 string) string {
	m, n := len(word1), len(word2)
	i, j := 0, 0
	var ans strings.Builder
	for i < m && j < n {
		if word1[i:] > word2[j:] {
			ans.WriteByte(word1[i])
			i++
		} else {
			ans.WriteByte(word2[j])
			j++
		}
	}
	ans.WriteString(word1[i:])
	ans.WriteString(word2[j:])
	return ans.String()
}

力扣原题 · Doocs 题解来源

1764. 通过连接另一个数组的子数组得到一个数组

中等1 种解法

标签：贪心、数组、双指针、字符串匹配、KMP 算法

题目、示例与约束

给你一个长度为 n 的二维整数数组 groups ，同时给你一个整数数组 nums 。

你是否可以从 nums 中选出 n 个 不相交 的子数组，使得第 i 个子数组与 groups[i] （下标从 0 开始）完全相同，且如果 i > 0 ，那么第 (i-1) 个子数组在 nums 中出现的位置在第 i 个子数组前面。（也就是说，这些子数组在 nums 中出现的顺序需要与 groups 顺序相同）

如果你可以找出这样的 n 个子数组，请你返回 true ，否则返回 false 。

如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组，就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。

示例 1：

输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出：true
解释：你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。
这两个子数组是不相交的，因为它们没有任何共同的元素。

示例 2：

输入：groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
输出：false
解释：选择子数组 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正确的，因为它们出现的顺序与 groups 中顺序不同。
[10,-2] 必须出现在 [1,2,3,4] 之前。

示例 3：

输入：groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
输出：false
解释：选择子数组 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正确的，因为它们不是不相交子数组。
它们有一个共同的元素 nums[4] （下标从 0 开始）。

提示：

groups.length == n
1 <= n <= 10³
1 <= groups[i].length, sum(groups[i].length) <= 10³
1 <= nums.length <= 10³
-10⁷ <= groups[i][j], nums[k] <= 10⁷

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

思考

要在 $n u m s$ 中按顺序找到互不重叠的子数组依次匹配 $g r o u p s$ 。组数与长度都很小，从左到右贪心匹配即可：能匹配当前组就消耗它，否则起点右移一格。

指针 $i$ 指向当前组、 $j$ 指向 $n u m s$ 。切片相等则 $j$ 跳过该组长度且 $i$ 加一，否则 $j$ 加一。 $i$ 走到组数则成功。

我们贪心地枚举 nums 中每一个数 $n u m s [j]$ 作为子数组的开始，判断其是否与当前 $g r o u p s [i]$ 匹配，是则将指针 $i$ 往后移一位，将指针 $j$ 往后移动 $g r o u p s [i] . l e n g t h$ 位，否则将指针 $j$ 往后移动一位。

如果 $i$ 走到了 $g r o u p s . l e n g t h$ ，说明所有的子数组都匹配上了，返回 true，否则返回 false。

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

func canChoose(groups [][]int, nums []int) bool {
	check := func(a, b []int, j int) bool {
		m, n := len(a), len(b)
		i := 0
		for ; i < m && j < n; i, j = i+1, j+1 {
			if a[i] != b[j] {
				return false
			}
		}
		return i == m
	}
	n, m := len(groups), len(nums)
	i := 0
	for j := 0; i < n && j < m; {
		if check(groups[i], nums, j) {
			j += len(groups[i])
			i++
		} else {
			j++
		}
	}
	return i == n
}

力扣原题 · Doocs 题解来源

1775. 通过最少操作次数使数组的和相等

中等2 种解法

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

题目、示例与约束

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择任意数组中的任意一个整数，将它变成 1 到 6 之间任意的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

提示：

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

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

思考

元素只能改到 $[1, 6]$ ，要让两数组和相等且改动次数最少。 $n \leq 10^{5}$ ，需按「一次改动能缩小的差距」贪心。

不妨设 $s_{1} < s_{2}$ 。较小数组每个数最多加到 $6$ ，较大数组最多减到 $1$ 。把这些增量收集后降序，能一次减多少差距就减多少，直到差距非正。

我们用 $s_{1}$ 和 $s_{2}$ 分别表示数组 nums1 和 nums2 的和。

如果 $s_{1} = s_{2}$ ，则不需要任何操作，直接返回 $0$ 。否则，我们不妨设 $s_{1} < s_{2}$ ，即 $n u m s_{1}$ 中的元素和小于 $n u m s_{2}$ 中的元素和，那么两个数组元素和的差值 $d = s_{2} - s_{1}$ 。

要使得两个数组元素和相等，我们需要对 nums1 中的元素进行增大操作，对 nums2 中的元素进行减小操作。

对于 nums1 中的每个元素 $v$ ，我们最多可以将其增大到 $6$ ，那么 $v$ 可以增大的量为 $6 - v$ 。对于 nums2 中的每个元素 $v$ ，我们最多可以将其减小到 $1$ ，那么 $v$ 可以减小的量为 $v - 1$ 。

我们将每个元素的变化量放入数组 arr 中，然后对数组 arr 进行降序排列。

接下来，我们从数组 arr 的第一个元素开始，贪心地将 $d$ 减去每个元素的变化量，直到 $d \leq 0$ ，返回此时的操作次数即可。

遍历结束后，如果 $d > 0$ ，说明无法使得两个数组元素和相等，返回 $- 1$ 。

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

func minOperations(nums1 []int, nums2 []int) int {
	s1, s2 := sum(nums1), sum(nums2)
	if s1 == s2 {
		return 0
	}
	if s1 > s2 {
		return minOperations(nums2, nums1)
	}
	d := s2 - s1
	arr := []int{}
	for _, v := range nums1 {
		arr = append(arr, 6-v)
	}
	for _, v := range nums2 {
		arr = append(arr, v-1)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(arr)))
	for i, v := range arr {
		d -= v
		if d <= 0 {
			return i + 1
		}
	}
	return -1
}

func sum(nums []int) (s int) {
	for _, v := range nums {
		s += v
	}
	return
}

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

思考

增量只可能是 $0. .5$ ，不必排序数组。用长度为 $6$ 的计数桶从 $5$ 扫到 $1$ ，按出现次数消耗差距，时间降为线性。

方法一中，我们需要创建数组 arr 并进行排序，时空复杂度较高。由于数组 arr 中元素的范围为 $[0, . .5]$ ，因此我们创建一个长度为 $6$ 的数组 cnt，用于统计数组 arr 中每个元素的数量，也即每个最大变化量的元素的数量。

接下来，我们从最大变化量 $i = 5$ 开始，贪心地将 $d$ 减去最大变化量，直到 $d \leq 0$ ，返回此时的操作次数即可。

时间复杂度 $O (m + n)$ ，空间复杂度 $O (C)$ 。其中 $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。本题中 $C = 6$ 。

func minOperations(nums1 []int, nums2 []int) (ans int) {
	s1, s2 := sum(nums1), sum(nums2)
	if s1 == s2 {
		return 0
	}
	if s1 > s2 {
		return minOperations(nums2, nums1)
	}
	d := s2 - s1
	cnt := [6]int{}
	for _, v := range nums1 {
		cnt[6-v]++
	}
	for _, v := range nums2 {
		cnt[v-1]++
	}
	for i := 5; i > 0; i-- {
		for cnt[i] > 0 && d > 0 {
			d -= i
			cnt[i]--
			ans++
		}
	}
	if d <= 0 {
		return
	}
	return -1
}

func sum(nums []int) (s int) {
	for _, v := range nums {
		s += v
	}
	return
}

力扣原题 · Doocs 题解来源

1785. 构成特定和需要添加的最少元素

中等1 种解法

标签：贪心、数组

题目、示例与约束

给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性：abs(nums[i]) <= limit 。

返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ，添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。

注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。

示例 1：

输入：nums = [1,-1,1], limit = 3, goal = -4
输出：2
解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。

示例 2：

输入：nums = [1,-10,9,1], limit = 100, goal = 0
输出：1

提示：

1 <= nums.length <= 10⁵
1 <= limit <= 10⁶
-limit <= nums[i] <= limit
-10⁹ <= goal <= 10⁹

方法一：贪心 · Go 实现

思考

可向数组追加绝对值不超过 $limit$ 的整数，使总和变为 $goal$ ，追加个数尽量少。

差距 $d = | \sum n u m s - goal |$ 每次最多缩小 $limit$ ，最少次数为 $⌈ d / limit ⌉$ 。

我们先计算数组元素总和 $s$ ，然后计算 $s$ 与 $g o a l$ 的差值 $d$ 。

那么需要添加的元素数量为 $d$ 的绝对值除以 $l i m i t$ 向上取整，即 $⌈ \frac{| d |}{l i m i t} ⌉$ 。

注意，本题中数组元素的数据范围为 $[- 10^{6}, 10^{6}]$ ，元素个数最大为 $10^{5}$ ，总和 $s$ 以及差值 $d$ 可能会超过 $32$ 位整数的表示范围，因此需要使用 $64$ 位整数。

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

func minElements(nums []int, limit int, goal int) int {
	s := 0
	for _, v := range nums {
		s += v
	}
	d := abs(s - goal)
	return (d + limit - 1) / limit
}

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

力扣原题 · Doocs 题解来源

1788. 最大化花园的美观度 🔒

困难1 种解法

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

题目、示例与约束

有一个花园，有 n 朵花，这些花都有一个用整数表示的美观度。这些花被种在一条线上。给定一个长度为 n 的整数类型数组 flowers ，每一个 flowers[i] 表示第 i 朵花的美观度。

一个花园满足下列条件时，该花园是有效的。

花园中至少包含两朵花。
第一朵花和最后一朵花的美观度相同。

作为一个被钦定的园丁，你可以从花园中去除任意朵花（也可以不去除任意一朵）。你想要通过一种方法移除某些花朵，使得剩下的花园变得有效。花园的美观度是其中所有剩余的花朵美观度之和。

返回你去除了任意朵花（也可以不去除任意一朵）之后形成的有效花园中最大可能的美观度。

示例 1：

输入: flowers = [1,2,3,1,2]
输出: 8
解释: 你可以修整为有效花园 [2,3,1,2] 来达到总美观度 2 + 3 + 1 + 2 = 8。

示例 2：

输入: flowers = [100,1,1,-3,1]
输出: 3
解释: 你可以修整为有效花园 [1,1,1] 来达到总美观度 1 + 1 + 1 = 3。

示例 3：

输入: flowers = [-1,-2,0,-1]
输出: -2
解释: 你可以修整为有效花园 [-1,-1] 来达到总美观度 -1 + -1 = -2。

提示：

2 <= flowers.length <= 10⁵
-10⁴ <= flowers[i] <= 10⁴
去除一些花朵（可能没有）后，是有可能形成一个有效花园的。

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

思考

有效花园两端花色相同，中间可删负值花。枚举左右同色端点，中间正数应全部保留。

哈希表记下每种美观度首次出现的位置，前缀和只累加正数。再次遇到 $v$ 时，用「两端各计一次 $v$ 、中间取正前缀和」更新答案。

我们用哈希表 $d$ 记录每个美观度第一次出现的位置，用前缀和数组 $s$ 记录当前位置之前的美观度之和。如果一个美观度 $v$ 在位置 $i$ 和 $j$ 出现过（其中 $i < j$ ），那么我们可以得到一个有效的花园 $[i + 1, j]$ ，其美观度为 $s [i] - s [j + 1] + v \times 2$ ，我们用这个值更新答案。否则，我们将当前美观度所在的位置 $i$ 记录到哈希表 $d$ 中。接下来，我们更新前缀和，如果美观度 $v$ 为负数，我们将其视为 $0$ 。

遍历完所有的美观度之后，我们就可以得到答案。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为花朵的数量。

func maximumBeauty(flowers []int) int {
	n := len(flowers)
	s := make([]int, n+1)
	d := map[int]int{}
	ans := math.MinInt32
	for i, v := range flowers {
		if j, ok := d[v]; ok {
			ans = max(ans, s[i]-s[j+1]+v*2)
		} else {
			d[v] = i
		}
		s[i+1] = s[i] + max(v, 0)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1792. 最大平均通过率

中等1 种解法

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

题目、示例与约束

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [pass_i, total_i] ，表示你提前知道了第 i 个班级总共有 total_i 个学生，其中只有 pass_i 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们一定能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得所有班级的平均通过率最大。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的最大平均通过率。与标准答案误差范围在 10^-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

提示：

1 <= classes.length <= 10⁵
classes[i].length == 2
1 <= pass_i <= total_i <= 10⁵
1 <= extraStudents <= 10⁵

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

思考

每个额外通过生只能进一个班，班级平均通过率的总和（再除以班数）要最大。增量 $\frac{a + 1}{b + 1} - \frac{a}{b}$ 随人数增加而递减，应每次把人分给当前增量最大的班。

用增量的相反数作小根堆（或直接按增量建堆）。分配一名学生后更新该班人数并重新入堆，最后求各班通过率均值。

假设一个班级当前的通过率为 $\frac{a}{b}$ ，那么如果我们将一个聪明的学生安排到此班级，那么班级的通过率就会变为 $\frac{a + 1}{b + 1}$ 。我们可以发现，通过率的增量为 $\frac{a + 1}{b + 1} - \frac{a}{b}$ 。

我们维护一个大根堆，堆中存储的是每个班级的通过率增量。

进行 extraStudents 次操作，每次从堆顶取出一个班级，将这个班级的人数和通过人数都加 $1$ ，然后将这个班级的通过率增量重新计算并放回堆中。重复这个过程，直到将所有的学生都分配完毕。

最后，我们将所有班级的通过率求和，然后除以班级数目，即为答案。

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

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
	pq := hp{}
	for _, e := range classes {
		a, b := e[0], e[1]
		x := float64(a+1)/float64(b+1) - float64(a)/float64(b)
		heap.Push(&pq, tuple{x, a, b})
	}
	for i := 0; i < extraStudents; i++ {
		e := heap.Pop(&pq).(tuple)
		a, b := e.a+1, e.b+1
		x := float64(a+1)/float64(b+1) - float64(a)/float64(b)
		heap.Push(&pq, tuple{x, a, b})
	}
	var ans float64
	for len(pq) > 0 {
		e := heap.Pop(&pq).(tuple)
		ans += float64(e.a) / float64(e.b)
	}
	return ans / float64(len(classes))
}

type tuple struct {
	x float64
	a int
	b int
}

type hp []tuple

func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
	a, b := h[i], h[j]
	return a.x > b.x
}
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.(tuple)) }
func (h *hp) Pop() any     { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

力扣原题 · Doocs 题解来源

1794. 统计距离最小的子串对个数 🔒

中等1 种解法

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

题目、示例与约束

输入数据为两个字符串firstString 和 secondString，两个字符串下标均从0开始，且均只包含小写的英文字符，请计算满足下列要求的下标四元组(i,j,a,b)的个数：

0 <= i <= j < firstString.length
0 <= a <= b < secondString.length
firstString字符串中从i位置到j位置的子串(包括j位置的字符)和secondString字符串从a位置到b位置的子串(包括b位置字符)相等
j-a的数值是所有符合前面三个条件的四元组中可能的最小值

返回符合上述 4 个条件的四元组的个数。

示例1：

输入：firstString = "abcd", secondString = "bccda"
输出：1
解释：(0,0,4,4)是唯一符合条件的四元组且其j-a的数值是最小的.

示例 2：

输入：firstString = "ab", secondString = "cd"
输出：0
解释：没有任何一个四元组能满足上述4个要求.

提示：

1 <= firstString.length, secondString.length <= 2 * 10⁵
两个输入字符串均只包含小写英文字符.

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

思考

四元组要求两段子串相等且 $j - a$ 最小。子串相等可收缩到单字符：取 $f i r s t S t r i n g$ 尽量靠左的字符与 $s e c o n d S t r i n g$ 尽量靠右的相同字符。

哈希表记下 $s e c o n d S t r i n g$ 每个字符最后出现的位置。扫 $f i r s t S t r i n g$ 的每个 $i$ ，用 $i - last [c]$ 更新全局最小差及其出现次数。

题目实际上要我们找到一个最小的下标 $i$ 和一个最大的下标 $j$ ，使得 $f i r s t S t r i n g [i]$ 与 $s e c o n d S t r i n g [j]$ 相等，且 $i - j$ 的值是所有满足条件的下标对中最小的。

因此，我们先用哈希表 $l a s t$ 记录 $s e c o n d S t r i n g$ 中每个字符最后一次出现的下标，然后遍历 $f i r s t S t r i n g$ ，对于每个字符 $c$ ，如果 $c$ 在 $s e c o n d S t r i n g$ 中出现过，则计算 $i - l a s t [c]$ ，如果 $i - l a s t [c]$ 的值小于当前最小值，则更新最小值，同时更新答案为 1；如果 $i - l a s t [c]$ 的值等于当前最小值，则答案加 1。

时间复杂度 $O (m + n)$ ，空间复杂度 $O (C)$ 。其中 $m$ 和 $n$ 分别是 $f i r s t S t r i n g$ 和 $s e c o n d S t r i n g$ 的长度，而 $C$ 是字符集的大小。本题中 $C = 26$ 。

func countQuadruples(firstString string, secondString string) (ans int) {
	last := [26]int{}
	for i, c := range secondString {
		last[c-'a'] = i + 1
	}
	mi := 1 << 30
	for i, c := range firstString {
		j := last[c-'a']
		if j > 0 {
			t := i - j
			if mi > t {
				mi = t
				ans = 1
			} else if mi == t {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1798. 你能构造出连续值的最大数目

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以构造出 x 。

请返回从 0 开始（包括 0 ），你最多能构造出多少个连续整数。

你可能有多个相同值的硬币。

示例 1：

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
从 0 开始，你可以构造出 2 个连续整数。

示例 2：

输入：coins = [1,1,1,4]
输出：8
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
- 2：取 [1,1]
- 3：取 [1,1,1]
- 4：取 [4]
- 5：取 [4,1]
- 6：取 [4,1,1]
- 7：取 [4,1,1,1]
从 0 开始，你可以构造出 8 个连续整数。

示例 3：

输入：nums = [1,4,10,3,1]
输出：20

提示：

coins.length == n
1 <= n <= 4 * 10⁴
1 <= coins[i] <= 4 * 10⁴

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

思考

用硬币的子集和去覆盖从 $0$ 起的一段连续整数，求这段能延伸到多长。若能做出 $[0, a n s)$ ，再加入 $v \leq a n s$ 的硬币可将区间扩到 $[0, a n s + v)$ 。

硬币排序后从小到大吃进：一旦 $v > a n s$ 出现空洞，停止。最终 $a n s$ 即为从 $0$ 起连续可构造的个数。

我们先对数组进行排序。然后定义 $a n s$ 表示当前能够构造的连续整数的个数，初始化为 $1$ 。

遍历数组，对于当前遍历到的元素 $v$ ，如果 $v > a n s$ ，说明无法构造出 $a n s + 1$ 个连续的整数，因此直接跳出循环，返回 $a n s$ 即可。否则，说明可以构造出 $a n s + v$ 个连续的整数，因此更新 $a n s$ 为 $a n s + v$ 。

最后返回 $a n s$ 即可。

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

func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins)
	ans := 1
	for _, v := range coins {
		if v > ans {
			break
		}
		ans += v
	}
	return ans
}

力扣原题 · Doocs 题解来源

1802. 有界数组中指定下标处的最大值

中等1 种解法

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

题目、示例与约束

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

nums.length == n
nums[i] 是 正整数 ，其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
nums 中所有元素之和不超过 maxSum
nums[index] 的值被 最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

示例 2：

输入：n = 6, index = 1,  maxSum = 10
输出：3

提示：

1 <= n <= maxSum <= 10⁹
0 <= index < n

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

思考

在相邻差至多为 $1$ 、总和不超过 $maxSum$ 的约束下，要使 $n u m s [index]$ 尽可能大。若从大到小枚举该位置的取值再构造全数组，单次校验已是 $O (n)$ ，而取值上界为 $maxSum$ ，无法承受。

一旦确定 $n u m s [index] = x$ ，为使总和最小，两侧应尽量按 $x - 1, x - 2, \dots$ 递减，触到 $1$ 后保持为 $1$ 。该最小和随 $x$ 单调递增，因此可对 $x$ 二分，并用闭式求和判断是否不超过 $maxSum$ 。函数 $sum (x, cnt)$ 按 $x$ 是否够填满 $cnt$ 个位置分两种情形计算。

根据题目描述，如果我们确定了 $n u m s [i n d e x]$ 的值为 $x$ ，此时我们可以找到一个最小的数组总和。也就是说，在 $i n d e x$ 左侧的数组元素从 $x - 1$ 一直递减到 $1$ ，如果还有剩余的元素，那么剩余的元素都为 $1$ ；同理，在 $i n d e x$ 及右侧的数组元素从 $x$ 一直递减到 $1$ ，如果还有剩余的元素，那么剩余的元素都为 $1$ 。

这样我们就可以计算出数组的总和，如果总和小于等于 $m a x S u m$ ，那么此时的 $x$ 是合法的。随着 $x$ 的增大，数组的总和也会增大，因此我们可以使用二分查找的方法，找到一个最大的且符合条件的 $x$ 。

为了方便计算数组左侧、右侧的元素之和，我们定义一个函数 $s u m (x, c n t)$ ，表示一共有 $c n t$ 个元素，且最大值为 $x$ 的数组的总和。函数 $s u m (x, c n t)$ 可以分为两种情况：

如果 $x \geq c n t$ ，那么数组的总和为 $\frac{(x + x - c n t + 1) \times c n t}{2}$
如果 $x < c n t$ ，那么数组的总和为 $\frac{(x + 1) \times x}{2} + c n t - x$

接下来，定义二分的左边界 $l e f t = 1$ ，右边界 $r i g h t = m a x S u m$ ，然后二分查找 $n u m s [i n d e x]$ 的值 $m i d$ ，如果 $s u m (m i d - 1, i n d e x) + s u m (m i d, n - i n d e x) \leq m a x S u m$ ，那么此时的 $m i d$ 是合法的，我们可以将 $l e f t$ 更新为 $m i d$ ，否则我们将 $r i g h t$ 更新为 $m i d - 1$ 。

最后将 $l e f t$ 作为答案返回即可。

时间复杂度 $O (\log M)$ ，其中 $M = m a x S u m$ 。空间复杂度 $O (1)$ 。

func maxValue(n int, index int, maxSum int) int {
	sum := func(x, cnt int) int {
		if x >= cnt {
			return (x + x - cnt + 1) * cnt / 2
		}
		return (x+1)*x/2 + cnt - x
	}
	return sort.Search(maxSum, func(x int) bool {
		x++
		return sum(x-1, index)+sum(x, n-index) > maxSum
	})
}

力扣原题 · Doocs 题解来源

1827. 最少操作使数组递增

简单1 种解法

标签：贪心、数组

题目、示例与约束

给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。

比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。

请你返回使 nums 严格递增 的最少操作次数。

我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

示例 1：

输入：nums = [1,1,1]
输出：3
解释：你可以进行如下操作：
1) 增加 nums[2] ，数组变为 [1,1,2] 。
2) 增加 nums[1] ，数组变为 [1,2,2] 。
3) 增加 nums[2] ，数组变为 [1,2,3] 。

示例 2：

输入：nums = [1,5,2,4,1]
输出：14

示例 3：

输入：nums = [8]
输出：0

提示：

1 <= nums.length <= 5000
1 <= nums[i] <= 10⁴

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

思考

每次只能把某个元素加一，要使数组严格递增且操作尽量少。若对每个位置枚举最终取值，搜索空间过大。

从左到右，前缀的最大值已经确定了后一项的下界。记当前应为 $m x + 1$ ，若 $v$ 不足则补到该值并计入差值，再把 $m x$ 更新为新的前缀最大。贪心一次扫描即可，因为多加只会抬高后续下界。

我们用变量 $m x$ 记录当前严格递增数组的最大值，初始时 $m x = 0$ 。

从左到右遍历数组 nums，对于当前遍历到的元素 $v$ ，如果 $v < m x + 1$ ，那么我们需要将其增加到 $m x + 1$ ，这样才能保证数组严格递增。因此，我们此次需要进行的操作次数为 $m a x (0, m x + 1 - v)$ ，累加到答案中，然后更新 $m x = m a x (m x + 1, v)$ 。继续遍历下一个元素，直到遍历完整个数组。

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

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

力扣原题 · Doocs 题解来源

1833. 雪糕的最大数量

中等1 种解法

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

题目、示例与约束

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意：Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

提示：

costs.length == n
1 <= n <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

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

思考

预算固定，买尽可能多支雪糕，顺序不限。若优先买贵的，数量一定不会更多。

按价格升序购买，直到下一支超过剩余硬币。排序后一次扫描即得最大支数。

要买尽可能多的雪糕，且可以按任意顺序购买，因此，我们应该优先选择定价小的雪糕。

对数组 costs 进行排序，然后从定价最小的雪糕开始，依次购买，直到不能购买为止，返回能购买的雪糕数量。

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

func maxIceCream(costs []int, coins int) int {
	sort.Ints(costs)
	for i, c := range costs {
		if coins < c {
			return i
		}
		coins -= c
	}
	return len(costs)
}

力扣原题 · Doocs 题解来源

1838. 最高频元素的频数

中等2 种解法

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

题目、示例与约束

元素的频数是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

示例 1：

输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

示例 2：

输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。

示例 3：

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

提示：

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

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

思考

每次把一个元素加一，最多 $k$ 次，求能达到的最大频数。目标值一定是原数组中的某个数，且操作对象应是不大于它的一段连续数。若枚举右端再暴力找左端， $n \leq 10^{5}$ 会超时。

排序后，长度 $m$ 可行则更短也可行，可二分频数。前缀和判断长为 $m$ 的窗口把全部元素抬到右端值的花费是否不超过 $k$ 。

根据题目描述，我们可以得出三个结论：

经过若干次操作后，数组中最高频元素一定是原数组中的某个元素。为什么呢？我们不妨假设操作的若干个元素分别为 $a_{1}, a_{2}, \dots, a_{m}$ ，其中最大值为 $a_{m}$ ，这几个元素都变成了同一个值 $x$ ，其中 $x \geq a_{m}$ ，那么也一定可以将这些元素全部变成 $a_{m}$ ，这样操作次数不会增加。
操作的若干个元素一定是排序后的数组的一段连续子数组。
如果一个频数 $m$ 满足条件，那么所有 $m^{'} < m$ 也满足条件。这启发我们可以考虑使用二分查找，找到最大的满足条件的频数。

因此，我们可以对数组 $n u m s$ 进行排序，然后计算排序后的数组的前缀和数组 $s$ ，其中 $s [i]$ 表示前 $i$ 个元素的和。

接下来，我们定义二分查找的左边界 $l = 1$ ，右边界 $r = n$ 。每一次二分查找，我们取中间值 $m = (l + r + 1) / 2$ ，然后检查是否存在一个长度为 $m$ 的连续子数组，使得这个子数组中的元素都可以变成数组中的某个元素，且操作次数不超过 $k$ 。如果存在这样的子数组，那么我们就可以将左边界 $l$ 更新为 $m$ ，否则将右边界 $r$ 更新为 $m - 1$ 。

最后返回左边界 $l$ 即可。

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

func maxFrequency(nums []int, k int) int {
	n := len(nums)
	sort.Ints(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	check := func(m int) bool {
		for i := m; i <= n; i++ {
			if nums[i-1]*m-(s[i]-s[i-m]) <= k {
				return true
			}
		}
		return false
	}
	l, r := 1, n
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

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

思考

方法一额外需要前缀和与二分。窗口花费随右端增大而单调，可用双指针： $i$ 右移时把窗口内已有元素都抬到 $n u m s [i]$ ，若花费超过 $k$ 则右移 $j$ 。线性扫一遍即可得到最大窗口。

我们也可以使用双指针来维护一个滑动窗口，窗口内中的元素都可以变成窗口中的最大值，窗口内元素的操作次数为 $s$ ，且 $s \leq k$ 。

初始时，我们将左指针 $j$ 指向数组的第一个元素，右指针 $i$ 也指向数组的第一个元素。接下来，我们每一次移动右指针 $i$ ，将窗口中的元素都变成 $n u m s [i]$ ，此时需要增加的操作次数为 $(n u m s [i] - n u m s [i - 1]) \times (i - j)$ 。如果这个操作次数超过了 $k$ ，那么我们就需要移动左指针 $j$ ，直到窗口内元素的操作次数不超过 $k$ 。然后，我们更新答案为窗口的长度的最大值。

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

func maxFrequency(nums []int, k int) int {
	sort.Ints(nums)
	ans := 1
	s := 0
	for i, j := 1, 0; i < len(nums); i++ {
		s += (nums[i] - nums[i-1]) * (i - j)
		for ; s > k; j++ {
			s -= nums[i] - nums[j]
		}
		ans = max(ans, i-j+1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1846. 减小和重新排列数组后的最大元素

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

arr 中 第一个 元素必须为 1 。
任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

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

减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

示例 1：

输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1]，该数组满足所有条件。
arr 中最大元素为 2 。

示例 2：

输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000]。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3]，满足所有条件。
arr 中最大元素为 3 。

示例 3：

输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

提示：

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

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

思考

可任意重排并把元素减小（不可增大），要求首项为 $1$ 且相邻差的绝对值不超过 $1$ ，同时最大化最大值。增大被禁止，故应尽量少减。

排序后令首项为 $1$ ，其后每一项至多比前一项大 $1$ ，超过则削到 $a r r [i - 1] + 1$ 。这样在满足约束的前提下保留了尽可能大的递增序列，末项即为答案。

我们先对数组进行排序，然后将数组的第一个元素设置为 $1$ 。

接下来，我们从第二个元素开始遍历数组，如果当前元素与前一个元素的差值大于 $1$ ，我们就贪心地将当前元素减小为前一个元素加 $1$ 。

最后，我们返回数组中最后一个元素的值。

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

func maximumElementAfterDecrementingAndRearranging(arr []int) int {
    slices.Sort(arr)

    arr[0] = 1
    for i := 1; i < len(arr); i++ {
        arr[i] = min(arr[i], arr[i-1]+1)
    }

    return arr[len(arr)-1]
}

力扣原题 · Doocs 题解来源

1850. 邻位交换的最小次数

中等1 种解法

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

题目、示例与约束

给你一个表示大整数的字符串 num ，和一个整数 k 。

如果某个整数是 num 中各位数字的一个排列且它的 值大于 num ，则称这个整数为妙数。可能存在很多妙数，但是只需要关注 值最小 的那些。

例如，num = "5489355142" ：
- 第 1 个最小妙数是 "5489355214"
- 第 2 个最小妙数是 "5489355241"
- 第 3 个最小妙数是 "5489355412"
- 第 4 个最小妙数是 "5489355421"

返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。

测试用例是按存在第 k 个最小妙数而生成的。

示例 1：

输入：num = "5489355142", k = 4
输出：2
解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
- 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
- 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"

示例 2：

输入：num = "11112", k = 4
输出：4
解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："11112" -> "11121"
- 交换下标 2 和下标 3 对应的位："11121" -> "11211"
- 交换下标 1 和下标 2 对应的位："11211" -> "12111"
- 交换下标 0 和下标 1 对应的位："12111" -> "21111"

示例 3：

输入：num = "00123", k = 1
输出：1
解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："00123" -> "00132"

提示：

2 <= num.length <= 1000
1 <= k <= 1000
num 仅由数字组成

方法一：求下一个排列 + 逆序对 · Go 实现

思考

先得到第 $k$ 个下一排列，再问原串用相邻交换变成它的最少次数。数字可重复，不能把位置一一对应成置换后再随意交换。

调用 $k$ 次下一排列得到目标 $s$ 。把原串每个数字的出现下标按顺序记下来，再按 $s$ 从左到右贪心取同数字的下一个下标，得到一个排列。相邻交换次数等于该排列的逆序对数。

我们可以调用 $k$ 次 next_permutation 函数，得到第 $k$ 个最小妙数 $s$ 。

接下来，我们只需要计算 $n u m$ 需要经过多少次交换才能变成 $s$ 即可。

我们先考虑一个简单的情况，即 $n u m$ 中的数字都不相同。在这种情况下，我们可以直接把 $n u m$ 中的数字字符映射为下标。例如 $n u m$ 等于 "54893"，而 $s$ 等于 "98345"。我们将 $n u m$ 中的每个数字映射为下标，即：

\begin{aligned} n u m [0] & = 5 & \to & 0 \\ n u m [1] & = 4 & \to & 1 \\ n u m [2] & = 8 & \to & 2 \\ n u m [3] & = 9 & \to & 3 \\ n u m [4] & = 3 & \to & 4 \end{aligned}

那么 $s$ 中的每个数字映射为下标，就是 "32410"。这样，将 $n u m$ 变成 $s$ 所需要的交换次数，就等于 $s$ 映射后的下标数组的逆序对数。

如果 $n u m$ 中存在相同的数字，那么我们可以使用一个数组 $d$ 来记录每个数字出现的下标，其中 $d [i]$ 表示数字 $i$ 出现的下标列表。为了使得交换次数尽可能少，在将 $s$ 映射为下标数组时，我们只需要按顺序贪心地选择 $d$ 中对应数字的下标即可。

最后，我们可以直接使用双重循环来计算逆序对数，也可以使用树状数组来优化。

时间复杂度 $O (n \times (k + n))$ ，空间复杂度 $O (n)$ 。其中 $n$ 是 $n u m$ 的长度。

func getMinSwaps(num string, k int) (ans int) {
	s := []byte(num)
	for ; k > 0; k-- {
		nextPermutation(s)
	}
	d := [10][]int{}
	for i, c := range num {
		j := int(c - '0')
		d[j] = append(d[j], i)
	}
	idx := [10]int{}
	n := len(s)
	arr := make([]int, n)
	for i, c := range s {
		j := int(c - '0')
		arr[i] = d[j][idx[j]]
		idx[j]++
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if arr[j] > arr[i] {
				ans++
			}
		}
	}
	return
}

func nextPermutation(nums []byte) bool {
	n := len(nums)
	i := n - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i < 0 {
		return false
	}
	j := n - 1
	for j >= 0 && nums[j] <= nums[i] {
		j--
	}
	nums[i], nums[j] = nums[j], nums[i]
	for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
	return true
}

力扣原题 · Doocs 题解来源

1864. 构成交替字符串需要的最小交换次数

中等1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的最小字符交换次数，如果无法完成转化，返回 -1 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。

任意两个字符都可以进行交换，不必相邻 。

示例 1：

输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。

示例 3：

输入：s = "1110"
输出：-1

提示：

1 <= s.length <= 1000
s[i] 的值为 '0' 或 '1'

方法一：计数 · Go 实现

思考

用交换把二进制串变成 $0101 \dots$ 或 $1010 \dots$ 。两种目标的 $0 / 1$ 个数必须与原串匹配，否则无解。

先比较 $n_{0}$ 与 $n_{1}$ ：相差超过 $1$ 则返回 $- 1$ ；相等则两种开头都试；否则只能以较多的字符开头。错位个数除以 $2$ 即交换次数，因为一次交换修正两个错位。

我们先统计字符串 $s$ 中字符 $0$ 和字符 $1$ 的个数，分别记为 $n_{0}$ 和 $n_{1}$ 。

如果 $n_{0}$ 和 $n_{1}$ 的绝对值大于 $1$ ，那么无法构成交替字符串，返回 $- 1$ 。

如果 $n_{0}$ 和 $n_{1}$ 相等，那么我们可以分别计算将字符串转化为以 $0$ 开头和以 $1$ 开头的交替字符串所需要的交换次数，取最小值。

如果 $n_{0}$ 和 $n_{1}$ 不相等，那么我们只需要计算将字符串转化为以字符个数较多的字符开头的交替字符串所需要的交换次数。

问题转换为：计算字符串 $s$ 转化为以字符 $c$ 开头的交替字符串所需要的交换次数。

我们定义一个函数 $calc (c)$ ，表示将字符串 $s$ 转化为以字符 $c$ 开头的交替字符串所需要的交换次数。我们遍历字符串 $s$ ，对于每个位置 $i$ ，如果 $i$ 与 $c$ 的奇偶性不同，那么我们需要交换这个位置的字符，计数器 $+ 1$ 。由于每次交换都会使两个位置的字符变得相同，因此最终的交换次数为计数器的一半。

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

func minSwaps(s string) int {
	n0 := strings.Count(s, "0")
	n1 := len(s) - n0
	if abs(n0-n1) > 1 {
		return -1
	}
	calc := func(c int) int {
		cnt := 0
		for i, ch := range s {
			x := int(ch - '0')
			if i&1^c != x {
				cnt++
			}
		}
		return cnt / 2
	}
	if n0 == n1 {
		return min(calc(0), calc(1))
	}
	if n0 > n1 {
		return calc(0)
	}
	return calc(1)
}

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

力扣原题 · Doocs 题解来源

1874. 两个数组的最小乘积和 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给定两个长度相等的数组a和b，它们的乘积和为数组中所有的a[i] * b[i]之和，其中0 <= i < a.length。

比如a = [1,2,3,4]，b = [5,2,3,1]时，它们的乘积和为1*5 + 2*2 + 3*3 + 4*1 = 22

现有两个长度都为n的数组nums1和nums2，你可以以任意顺序排序nums1，请返回它们的最小乘积和。

示例 1:

输入: nums1 = [5,3,4,2], nums2 = [4,2,2,5]
输出: 40
解释: 将 num1 重新排列为 [3,5,4,2] 后，可由 [3,5,4,2] 和 [4,2,2,5] 得到最小乘积和 3*4 + 5*2 + 4*2 + 2*5 = 40。

示例 2:

输入: nums1 = [2,1,4,5,7], nums2 = [3,2,4,8,6]
输出: 65
解释: 将 num1 重新排列为 [5,7,4,1,2] 后，可由 [5,7,4,1,2] 和 [3,2,4,8,6] 得到最小乘积和 5*3 + 7*2 + 4*4 + 1*8 + 2*6 = 65。

提示:

n == nums1.length == nums2.length
1 <= n <= 10⁵
1 <= nums1[i], nums2[i] <= 100

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

思考

两数组对应相乘再求和，其中一个可任意重排，求最小乘积和。正数情形下，大数应配小数。

将 $n u m s 1$ 升序、 $n u m s 2$ 降序后对应相乘累加，即重新排列中的最小点积。

由于两个数组都是正整数，要使得乘积和最小，我们可以将两个数组中的最大值和最小值相乘，次大值和次小值相乘，以此类推。

因此，我们将数组 $nums1$ 按照升序排序，将数组 $nums2$ 按照降序排序，然后将两个数组对应位置的元素相乘，累加即可。

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

func minProductSum(nums1 []int, nums2 []int) (ans int) {
	sort.Ints(nums1)
	sort.Ints(nums2)
	for i, x := range nums1 {
		ans += x * nums2[len(nums2)-1-i]
	}
	return
}

力扣原题 · Doocs 题解来源

1877. 数组中最大数对和的最小值

中等1 种解法

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

题目、示例与约束

一对元素 (a,b) 的 数对和 等于 a + b。最大数对和 是所有数对中最大的 数对和。

例如，如果有数对 (1,5)、(2,3) 和 (4,4)，那么 最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8。

给你一个长度为偶数 n 的数组 nums，请你将 nums 中的元素分成 n / 2 个数对，使得：

nums 中的每个元素 恰好属于一个 数对，并且
最大数对和 尽可能小。

请你返回最优配对方案下 最大数对和 的最小值。

示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：可以将元素分成数对 (3,3) 和 (5,2)。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7。

示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：可以将元素分成数对 (3,5)、(4,4) 和 (6,2)。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8。

提示：

n == nums.length
2 <= n <= 10⁵
n 是偶数。
1 <= nums[i] <= 10⁵

方法一：贪心 · Go 实现

思考

把数组两两配对，使最大数对和尽量小。若两大数配对，该和必然偏大。

排序后最小与最大配对、次小与次大配对，取这些和的最大值。这样避免两个大数落在同一对。

要使得数组中最大数对和的值最小，那么我们可以将数组中最小的数和最大的数配对，次小的数和次大的数配对，依此类推。

因此，我们可以先对数组进行排序，然后使用两个指针分别指向数组的两端，求出两个指针指向的数的和，更新最大数对和的值，然后将左指针右移一位，右指针左移一位，继续进行操作，直到两个指针相遇为止，即可得到最小的最大数对和。

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

func minPairSum(nums []int) (ans int) {
	sort.Ints(nums)
	n := len(nums)
	for i, x := range nums[:n>>1] {
		ans = max(ans, x+nums[n-1-i])
	}
	return
}

力扣原题 · Doocs 题解来源

1881. 插入后的最大值

中等1 种解法

标签：贪心、字符串

题目、示例与约束

给你一个非常大的整数 n 和一个整数数字 x ，大整数 n 用一个字符串表示。n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中，且 n 可能表示一个负数。

你打算通过在 n 的十进制表示的任意位置插入 x 来 最大化 n 的数值。但不能在负号的左边插入 x 。

例如，如果 n = 73 且 x = 6 ，那么最佳方案是将 6 插入 7 和 3 之间，使 n = 763 。
如果 n = -55 且 x = 2 ，那么最佳方案是将 2 插在第一个 5 之前，使 n = -255 。

返回插入操作后，用字符串表示的 n 的最大值。

示例 1：

输入：n = "99", x = 9
输出："999"
解释：不管在哪里插入 9 ，结果都是相同的。

示例 2：

输入：n = "-13", x = 2
输出："-123"
解释：向 n 中插入 x 可以得到 -213、-123 或者 -132 ，三者中最大的是 -123 。

提示：

1 <= n.length <= 10⁵
1 <= x <= 9
n 中每一位的数字都在闭区间 [1, 9] 中。
n 代表一个有效的整数。
当 n 表示负数时，将会以字符 '-' 开始。

方法一：贪心 · Go 实现

思考

把数字 $x$ 插入十进制串 $n$ 的某一位置，使数值最大。正数应尽早出现更大的高位，负数则相反。

正数找到第一位小于 $x$ 的位置插入；负数跳过符号后找到第一位大于 $x$ 的位置插入。这样高位按符号方向变得更优。

如果 $n$ 是负数，那么我们要找到第一个大于 $x$ 的位置，然后在这个位置插入 $x$ ；如果 $n$ 是正数，那么我们要找到第一个小于 $x$ 的位置，然后在这个位置插入 $x$ 。

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

func maxValue(n string, x int) string {
	i := 0
	y := byte('0' + x)
	if n[0] == '-' {
		i++
		for i < len(n) && n[i] <= y {
			i++
		}
	} else {
		for i < len(n) && n[i] >= y {
			i++
		}
	}
	return n[:i] + string(y) + n[i:]
}

力扣原题 · Doocs 题解来源

LeetCode Go · 贪心（5） ​

1702. 修改后的最大二进制字符串 ​

1703. 得到连续 K 个 1 的最少相邻交换次数 ​

1705. 吃苹果的最大数目 ​

1708. 长度为 K 的最大子数组 🔒 ​

1710. 卡车上的最大单元数 ​

1713. 得到子序列的最少操作次数 ​

1717. 删除子字符串的最大得分 ​

1727. 重新排列后的最大子矩阵 ​

1733. 需要教语言的最少人数 ​

1736. 替换隐藏数字得到的最晚时间 ​

1739. 放置盒子 ​

1753. 移除石子的最大得分 ​

1754. 构造字典序最大的合并字符串 ​

1764. 通过连接另一个数组的子数组得到一个数组 ​

1775. 通过最少操作次数使数组的和相等 ​

1785. 构成特定和需要添加的最少元素 ​

1788. 最大化花园的美观度 🔒 ​

1792. 最大平均通过率 ​

1794. 统计距离最小的子串对个数 🔒 ​

1798. 你能构造出连续值的最大数目 ​

1802. 有界数组中指定下标处的最大值 ​

1827. 最少操作使数组递增 ​

1833. 雪糕的最大数量 ​

1838. 最高频元素的频数 ​

1846. 减小和重新排列数组后的最大元素 ​

1850. 邻位交换的最小次数 ​

1864. 构成交替字符串需要的最小交换次数 ​

1874. 两个数组的最小乘积和 🔒 ​

1877. 数组中最大数对和的最小值 ​

1881. 插入后的最大值 ​

继续阅读

LeetCode Go · 贪心（5）

1702. 修改后的最大二进制字符串

1703. 得到连续 K 个 1 的最少相邻交换次数

1705. 吃苹果的最大数目

1708. 长度为 K 的最大子数组 🔒

1710. 卡车上的最大单元数

1713. 得到子序列的最少操作次数

1717. 删除子字符串的最大得分

1727. 重新排列后的最大子矩阵

1733. 需要教语言的最少人数

1736. 替换隐藏数字得到的最晚时间

1739. 放置盒子

1753. 移除石子的最大得分

1754. 构造字典序最大的合并字符串

1764. 通过连接另一个数组的子数组得到一个数组

1775. 通过最少操作次数使数组的和相等

1785. 构成特定和需要添加的最少元素

1788. 最大化花园的美观度 🔒

1792. 最大平均通过率

1794. 统计距离最小的子串对个数 🔒

1798. 你能构造出连续值的最大数目

1802. 有界数组中指定下标处的最大值

1827. 最少操作使数组递增

1833. 雪糕的最大数量

1838. 最高频元素的频数

1846. 减小和重新排列数组后的最大元素

1850. 邻位交换的最小次数

1864. 构成交替字符串需要的最小交换次数

1874. 两个数组的最小乘积和 🔒

1877. 数组中最大数对和的最小值

1881. 插入后的最大值