LeetCode Go · 贪心（1）

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

来源与许可

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

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

11. 盛最多水的容器

中等1 种解法

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

题目、示例与约束

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

 

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

 

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

方法一：双指针 · Go 实现

思考

若枚举所有下标对 $(i,j)$，面积为 $min(height[i],height[j])\times (j-i)$，时间复杂度为 $O(n^2)$。 $n\le {10}^5$，无法通过。

容器的高度由较短的那根线决定。从最宽的区间 $[0,n-1]$ 出发：若向内移动较高的一端，宽度减小，高度仍受较短边限制，面积不会变大。因此每次应当舍弃较短的那根，尝试碰到更高的边。用左右指针向中间收缩，每次移动较矮的一侧，每个下标至多访问一次。

我们使用两个指针 $l$ 和 $r$ 分别指向数组的左右两端，即 $l=0$，而 $r=n-1$，其中 $n$ 是数组的长度。

接下来，我们使用变量 $\mathit{\text{ans}}$ 记录容器的最大容量，初始化为 $0$。

然后，我们开始进行循环，每次循环中，我们计算当前容器的容量，即 $\mathit{\text{min}}(height[l],height[r])\times (r-l)$，并将其与 $\mathit{\text{ans}}$ 进行比较，将较大值赋给 $\mathit{\text{ans}}$。然后，我们判断 $height[l]$ 和 $height[r]$ 的大小，如果 $\mathit{\text{height}}[l]<\mathit{\text{height}}[r]$，移动 $r$ 指针不会使得结果变得更好，因为容器的高度由较短的那根垂直线决定，所以我们移动 $l$ 指针。反之，我们移动 $r$ 指针。

遍历结束后，返回 $\mathit{\text{ans}}$ 即可。

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

func maxArea(height []int) (ans int) {
	l, r := 0, len(height)-1
	for l < r {
		t := min(height[l], height[r]) * (r - l)
		ans = max(ans, t)
		if height[l] < height[r] {
			l++
		} else {
			r--
		}
	}
	return
}

力扣原题 · Doocs 题解来源

134. 加油站

中等1 种解法

标签：贪心、数组

题目、示例与约束

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

 

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

 

提示:

• n == gas.length == cost.length
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104
• 输入保证答案唯一。

方法一：从任意起点开始遍历 · Go 实现

思考

问能否走完一圈以及从哪一站出发。 $n\le {10}^5$，从每个起点模拟一圈是 $O(n^2)$。总油量小于总消耗则无解。

从某站出发油量为负，说明起点必须更靠前才能「补贴」这段亏空。代码从末站起向前扩起点、向后扩终点，亏空时把 $i$ 左移补油，每个站进出一次，最后看剩余是否非负。

我们用 $i$, $j$ 分别标记起点和终点，用 $s$ 表示当前剩余汽油，而 $cnt$ 表示当前行驶过的加油站数量。初始时，我们将起点设在最后一个位置，即 $i=n-1$。

开始行驶，移动 $j$。若发现当前剩余汽油小于 $0$，说明当前 $i$ 作为起点不符合要求，我们将起点 $i$ 循环左移，并且更新剩余汽油，直至剩余汽油是非负数。

当行驶过的加油站数量达到 $n$ 时，结束行驶过程。若此时剩余汽油 $s$ 仍然小于 $0$，说明不存在这样的起点，返回 $-1$。否则，返回起点 $i$。

时间复杂度 $O(n)$，其中 $n$ 表示加油站的数量。空间复杂度 $O(1)$。

func canCompleteCircuit(gas []int, cost []int) int {
	n := len(gas)
	i, j := n-1, n-1
	cnt, s := 0, 0
	for cnt < n {
		s += gas[j] - cost[j]
		cnt++
		j = (j + 1) % n
		for s < 0 && cnt < n {
			i--
			s += gas[i] - cost[i]
			cnt++
		}
	}
	if s < 0 {
		return -1
	}
	return i
}

力扣原题 · Doocs 题解来源

135. 分发糖果

困难1 种解法

标签：贪心、数组

题目、示例与约束

n 个孩子站成一排。

给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子 至少 分配到 1 个糖果。
• 相邻两个孩子中，评分 更高 的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少 糖果数目。

 

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

 

提示：

• 1 <= n == ratings.length <= 5 * 104
• 0 <= ratings[i] <= 5 * 104

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

思考

相邻评分更高的人必须拿更多糖，求最少总数。 $n\le 5\times {10}^4$，按评分排序再分配可以，但要小心相等评分。左右约束互相独立：从左扫一遍满足「比左边高则多一颗」，从右再扫一遍满足右边，每人取两侧要求的较大值，两边的递增链都不会被破坏。

我们初始化两个数组 $left$ 和 $right$，其中 $left[i]$ 表示当前孩子比左边孩子评分高时，当前孩子至少应该获得的糖果数，而 $right[i]$ 表示当前孩子比右边孩子评分高时，当前孩子至少应该获得的糖果数。初始时 $left[i]=1$, $right[i]=1$。

我们从左到右遍历一遍，如果当前孩子比左边孩子评分高，则 $left[i]=left[i-1]+1$；同理，我们从右到左遍历一遍，如果当前孩子比右边孩子评分高，则 $right[i]=right[i+1]+1$。

最后，我们遍历一遍评分数组，每个孩子至少应该获得的糖果数为 $left[i]$ 和 $right[i]$ 中的最大值，将它们累加起来即为答案。

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

func candy(ratings []int) int {
	n := len(ratings)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = 1
		right[i] = 1
	}
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	ans := 0
	for i, a := range left {
		b := right[i]
		ans += max(a, b)
	}
	return ans
}

力扣原题 · Doocs 题解来源

179. 最大数

中等1 种解法

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

题目、示例与约束

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

 

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

 

提示：

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

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

思考

拼接出一个最大整数。按数值或普通字典序排序都不对： $9$ 应排在 $98$ 前面，因为 $998>989$。 $n\le 100$。比较 $a+b$ 与 $b+a$ 即可决定两串的先后，整体按这个比较排序再拼接；若最高位是 $0$，说明全是 $0$，返回 $\mathtt{\text{"0"}}$。

先转成字符串列表，再对字符串列表进行字典序降序排列。最后将列表所有字符串拼接即可。

func largestNumber(nums []int) string {
	vs := make([]string, len(nums))
	for i, v := range nums {
		vs[i] = strconv.Itoa(v)
	}
	sort.Slice(vs, func(i, j int) bool {
		return vs[i]+vs[j] > vs[j]+vs[i]
	})
	if vs[0] == "0" {
		return "0"
	}
	return strings.Join(vs, "")
}

力扣原题 · Doocs 题解来源

253. 会议室 II 🔒

中等2 种解法

标签：贪心、数组、双指针、前缀和、排序、堆（优先队列）

题目、示例与约束

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

 

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：

输入：intervals = [[7,10],[2,4]]
输出：1

 

提示：

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

方法一：差分数组 · Go 实现

思考

所需会议室数等于同一时刻正在进行的会议数的最大值。在开始处 $+1$、结束处 $-1$，前缀和即当前占用。

用差分数组覆盖到最大结束时间，再扫一遍取前缀和的峰值。

我们可以用差分数组来实现。

我们首先找到所有会议的最大结束时间，记为 $m$，然后创建一个长度为 $m+1$ 的差分数组 $d$，将每个会议的开始时间和结束时间分别加到差分数组的对应位置上，即 $d[l]=d[l]+1$，而 $d[r]=d[r]-1$。

然后，我们计算差分数组的前缀和，找出前缀和的最大值，即为所需会议室的最小数量。

时间复杂度 $O(n+m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为会议数量和最大结束时间。

func minMeetingRooms(intervals [][]int) (ans int) {
	m := 0
	for _, e := range intervals {
		m = max(m, e[1])
	}

	d := make([]int, m+1)
	for _, e := range intervals {
		d[e[0]]++
		d[e[1]]--
	}

	s := 0
	for _, v := range d {
		s += v
		ans = max(ans, s)
	}
	return
}

方法二：差分（哈希表） · Go 实现

思考

结束时间很大时，长度为 $m$ 的数组浪费空间。改用哈希表只在出现过的端点上加减，按键排序后同样求前缀和最大值。

如果题目中的会议时间跨度很大，那么我们可以使用哈希表来代替差分数组。

我们首先创建一个哈希表 $d$，将每个会议的开始时间和结束时间分别加到哈希表的对应位置上，即 $d[l]=d[l]+1$，而 $d[r]=d[r]-1$。

然后，我们将哈希表按照键进行排序，计算哈希表的前缀和，找出前缀和的最大值，即为所需会议室的最小数量。

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

func minMeetingRooms(intervals [][]int) (ans int) {
	d := make(map[int]int)
	for _, e := range intervals {
		d[e[0]]++
		d[e[1]]--
	}

	keys := make([]int, 0, len(d))
	for k := range d {
		keys = append(keys, k)
	}
	sort.Ints(keys)

	s := 0
	for _, k := range keys {
		s += d[k]
		ans = max(ans, s)
	}
	return
}

力扣原题 · Doocs 题解来源

280. 摆动排序 🔒

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]... 

输入数组总是有一个有效的答案。

 

示例 1:

输入：nums = [3,5,2,1,6,4]
输出：[3,5,1,6,2,4]
解释：[1,6,2,5,3,4]也是有效的答案

示例 2:

输入：nums = [6,6,5,6,3,8]
输出：[6,6,5,6,3,8]

 

提示：

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 104

• 输入的 nums 保证至少有一个答案。

 

进阶：你能在 O(n) 时间复杂度下解决这个问题吗？

方法一 · Go 实现

思考

摆动只需相邻满足 $a_0\le a_1\ge a_2\le a_3\cdots$，不必全局排序。从左扫到每个位置，若与前一项关系不符则交换。

奇数位应不小于前一项，偶数位应不大于前一项；局部交换不会破坏更早已经摆好的相邻对。

func wiggleSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		if (i%2 == 1 && nums[i] < nums[i-1]) || (i%2 == 0 && nums[i] > nums[i-1]) {
			nums[i], nums[i-1] = nums[i-1], nums[i]
		}
	}
}

力扣原题 · Doocs 题解来源

316. 去除重复字母

中等2 种解法

标签：栈、贪心、字符串、单调栈

题目、示例与约束

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

 

示例 1：

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

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

 

提示：

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

 

注意：该题与 1081 https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters 相同

方法一：栈 · Go 实现

思考

求最小字典序的去重子序列，且须用尽每种出现过的字符各一次。若在全部子序列中选最小者，状态过多。

记录每字符最后出现位置。从左扫描，已在栈中则跳过；否则在栈顶更大且后面还会出现时弹出，再压入当前字符。单调栈保证局部最小，最后出现位置保证弹出仍可补回。

我们用一个数组 last 记录每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 vis 或者一个整型变量 mask 记录当前字符是否在栈中。

遍历字符串 $s$，对于每个字符 $c$，如果 $c$ 不在栈中，我们就需要判断栈顶元素是否大于 $c$，如果大于 $c$，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 $c$ 压入栈中。

最后将栈中元素拼接成字符串作为结果返回。

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

func removeDuplicateLetters(s string) string {
	last := make([]int, 26)
	for i, c := range s {
		last[c-'a'] = i
	}
	stk := []rune{}
	vis := make([]bool, 128)
	for i, c := range s {
		if vis[c] {
			continue
		}
		for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
			vis[stk[len(stk)-1]] = false
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, c)
		vis[c] = true
	}
	return string(stk)
}

方法二 · Go 实现

思考

方法一用最后下标判断「后面是否还有」。改为先统计频次，扫描时递减，栈顶剩余次数仍为正即可弹出。判定条件等价，不必预存最后位置。

func removeDuplicateLetters(s string) string {
	count, in_stack, stack := make([]int, 128), make([]bool, 128), make([]rune, 0)
	for _, c := range s {
		count[c] += 1
	}

	for _, c := range s {
		count[c] -= 1
		if in_stack[c] {
			continue
		}
		for len(stack) > 0 && stack[len(stack)-1] > c && count[stack[len(stack)-1]] > 0 {
			peek := stack[len(stack)-1]
			stack = stack[0 : len(stack)-1]
			in_stack[peek] = false
		}
		stack = append(stack, c)
		in_stack[c] = true
	}
	return string(stack)
}

力扣原题 · Doocs 题解来源

321. 拼接最大数

困难1 种解法

标签：栈、贪心、数组、双指针、单调栈

题目、示例与约束

给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。

请你利用这两个数组中的数字创建一个长度为 k <= m + n 的最大数。同一数组中数字的相对顺序必须保持不变。

返回代表答案的长度为 k 的数组。

 

示例 1：

输入：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
输出：[9,8,6,5,3]

示例 2：

输入：nums1 = [6,7], nums2 = [6,0,4], k = 5
输出：[6,7,6,0,4]

示例 3：

输入：nums1 = [3,9], nums2 = [8,9], k = 3
输出：[9,8,9]

 

提示：

• m == nums1.length
• n == nums2.length
• 1 <= m, n <= 500
• 0 <= nums1[i], nums2[i] <= 9
• 1 <= k <= m + n
• nums1 和 nums2 没有前导 0。

方法一：枚举 + 单调栈 · Go 实现

思考

要从两数组按相对顺序各取若干位，拼成长度为 $k$ 的最大数。单一单调栈只能处理一个数组。

枚举从 $nums1$ 取 $x$ 位（可行范围内），两数组分别用单调栈抽长度为 $x$ 与 $k-x$ 的最大子序列，再按字典序归并。比较所有 $x$ 的合并结果取最大。归并时相等前缀须递归看后面，以免局部贪心出错。

我们可以枚举从数组 $nums1$ 中取出 $x$ 个数，那么从数组 $nums2$ 中就需要取出 $k-x$ 个数。其中 $x\in [max(0,k-n),min(k,m)]$。

对于每一个 $x$，我们可以使用单调栈求出数组 $nums1$ 中长度为 $x$ 的最大子序列，以及数组 $nums2$ 中长度为 $k-x$ 的最大子序列。然后将这两个子序列合并得到长度为 $k$ 的最大子序列。

最后，我们比较所有的长度为 $k$ 的最大子序列，找出最大的序列即可。

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

func maxNumber(nums1 []int, nums2 []int, k int) []int {
	m, n := len(nums1), len(nums2)
	l, r := max(0, k-n), min(k, m)
	f := func(nums []int, k int) []int {
		n := len(nums)
		stk := make([]int, k)
		top := -1
		remain := n - k
		for _, x := range nums {
			for top >= 0 && stk[top] < x && remain > 0 {
				top--
				remain--
			}
			if top+1 < k {
				top++
				stk[top] = x
			} else {
				remain--
			}
		}
		return stk
	}

	var compare func(nums1, nums2 []int, i, j int) bool
	compare = func(nums1, nums2 []int, i, j int) bool {
		if i >= len(nums1) {
			return false
		}
		if j >= len(nums2) {
			return true
		}
		if nums1[i] > nums2[j] {
			return true
		}
		if nums1[i] < nums2[j] {
			return false
		}
		return compare(nums1, nums2, i+1, j+1)
	}

	merge := func(nums1, nums2 []int) []int {
		m, n := len(nums1), len(nums2)
		ans := make([]int, m+n)
		i, j := 0, 0
		for k := range ans {
			if compare(nums1, nums2, i, j) {
				ans[k] = nums1[i]
				i++
			} else {
				ans[k] = nums2[j]
				j++
			}
		}
		return ans
	}

	ans := make([]int, k)
	for x := l; x <= r; x++ {
		arr1 := f(nums1, x)
		arr2 := f(nums2, k-x)
		arr := merge(arr1, arr2)
		if compare(arr, ans, 0, 0) {
			ans = arr
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

324. 摆动排序 II

中等2 种解法

标签：贪心、数组、分治、快速选择、排序

题目、示例与约束

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

 

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：

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

 

提示：

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 5000
• 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

 

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

方法一：排序 · Go 实现

思考

要求 $nums[0]<nums[1]>nums[2]<\cdots$，且原数组无此序。就地重排即可，不必稳定。

排序后从中位数向前取小的放偶数位、从末尾向前取大的放奇数位，可避免相邻相等。中位数与最大值反向填充，使相等元素被隔开。

func wiggleSort(nums []int) {
	n := len(nums)
	arr := make([]int, n)
	copy(arr, nums)
	sort.Ints(arr)
	i, j := (n-1)>>1, n-1
	for k := 0; k < n; k++ {
		if k%2 == 0 {
			nums[k] = arr[i]
			i--
		} else {
			nums[k] = arr[j]
			j--
		}
	}
}

方法二：桶排序 · Go 实现

思考

方法一需要 $O(n\log n)$ 排序与额外数组。值域为 $[0,5000]$，用桶计数后从大到小先填奇数位再填偶数位，同样把大数放峰、小数放谷，时间线性。

func wiggleSort(nums []int) {
	bucket := make([]int, 5001)
	for _, v := range nums {
		bucket[v]++
	}
	n, j := len(nums), 5000
	for i := 1; i < n; i += 2 {
		for bucket[j] == 0 {
			j--
		}
		nums[i] = j
		bucket[j]--
	}
	for i := 0; i < n; i += 2 {
		for bucket[j] == 0 {
			j--
		}
		nums[i] = j
		bucket[j]--
	}
}

力扣原题 · Doocs 题解来源

330. 按要求补齐数组

困难1 种解法

标签：贪心、数组

题目、示例与约束

给定一个已排序的正整数数组 nums ，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。

请返回 满足上述要求的最少需要补充的数字个数 。

 

示例 1:

输入: nums = [1,3], n = 6
输出: 1 
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。

示例 2:

输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2,4]。

示例 3:

输入: nums = [1,2,2], n = 5
输出: 0

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• nums 按 升序排列
• 1 <= n <= 231 - 1

方法一：贪心 · Go 实现

思考

已有升序数组，可插入若干正整数，使 $[1,n]$ 均可被子集和表示。若对每个缺口暴力搜索插入值，状态过多。

设当前已覆盖 $[1,x)$。若下一项 $nums[i]\le x$，则并入后覆盖扩到 $[1,x+nums[i])$；否则贪心插入 $x$ 本身，覆盖翻倍。插入更小的数覆盖更窄，因此每次补当前缺口最优。直到 $x>n$。

我们假设数字 $x$ 是最小的不能表示的正整数，那么 $[1,..x-1]$ 的这些数都是可以表示的。为了能表示数字 $x$，我们需要添加一个小于等于 $x$ 的数：

• 如果添加的数等于 $x$，由于 $[1,..x-1]$ 的数都可以表示，添加 $x$ 后，区间 $[1,..2x-1]$ 内的数都可以表示，最小的不能表示的正整数变成了 $2x$。
• 如果添加的数小于 $x$，不妨设为 $x^{\prime }$，由于 $[1,..x-1]$ 的数都可以表示，添加 $x^{\prime }$ 后，区间 $[1,..x+x^{\prime }-1]$ 内的数都可以表示，最小的不能表示的正整数变成了 $x+x^{\prime }<2x$。

因此，我们应该贪心地添加数字 $x$，这样可以覆盖的区间更大。

我们用一个变量 $x$ 记录当前不能表示的最小正整数，初始化为 $1$，此时 $[1,..x-1]$ 是空的，表示当前没有任何数可以被覆盖；用一个变量 $i$ 记录当前遍历到的数组下标。

循环进行以下操作：

• 如果 $i$ 在数组范围内且 $nums[i]\le x$，说明当前数字可以被覆盖，因此将 $x$ 的值加上 $nums[i]$，并将 $i$ 的值加 $1$。
• 否则，说明 $x$ 没有被覆盖，因此需要在数组中补充一个数 $x$，然后 $x$ 更新为 $2x$。
• 重复上述操作，直到 $x$ 的值大于 $n$。

最终答案即为补充的数的数量。

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

func minPatches(nums []int, n int) (ans int) {
	x := 1
	for i := 0; x <= n; {
		if i < len(nums) && nums[i] <= x {
			x += nums[i]
			i++
		} else {
			ans++
			x <<= 1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

334. 递增的三元子序列

中等1 种解法

标签：贪心、数组、最长上升子序列

题目、示例与约束

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：

输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3：

输入：nums = [2,1,5,0,4,6]
输出：true
解释：其中一个满足题意的三元组是 (1, 4, 5)，因为 nums[1] == 1 < nums[4] == 4 < nums[5] == 6

 

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

 

进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

方法一 · Go 实现

思考

判断是否存在下标递增且值严格递增的三元组。枚举中间点为 $O(n^2)$。只需知道左侧更小值与当前可接的第二小值。

维护 $mi<mid$，扫描时：大于 $mid$ 则已构成三元；否则若不大于 $mi$ 则更新 $mi$，不然更新 $mid$。 $mid$ 的原下标不必保存，因其一定出现在更小的 $mi$ 之后。

func increasingTriplet(nums []int) bool {
	min, mid := math.MaxInt32, math.MaxInt32
	for _, num := range nums {
		if num > mid {
			return true
		}
		if num <= min {
			min = num
		} else {
			mid = num
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

358. K 距离间隔重排字符串 🔒

困难1 种解法

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

题目、示例与约束

给你一个非空的字符串 s 和一个整数 k ，你要将这个字符串 s 中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离 至少 为 k 。如果无法做到，请返回一个空字符串 ""。

 

示例 1：

输入: s = "aabbcc", k = 3
输出: "abcabc" 
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

示例 2:

输入: s = "aaabc", k = 3
输出: "" 
解释: 没有办法找到可能的重排结果。

示例 3:

输入: s = "aaadbbcc", k = 2
输出: "abacabcd"
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

 

提示：

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

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

思考

重排使相同字母间距至少为 $k$。若间隔不够则无解。应优先消耗频次高的字母，并用冷却队列保证间距。

大根堆按剩余次数取字母，写入后再放入长度为 $k$ 的冷却队列；队满则把仍有剩余的字母压回堆。若堆空而字符串未写完，说明冷却无法排开，返回空串。

我们用一个哈希表或数组 $\mathit{\text{cnt}}$ 来统计字符串中每个字母出现的次数，然后用一个大根堆 $\mathit{\text{pq}}$ 来存储每个字母及其出现次数。堆中的每个元素是一个二元组 $(v,c)$，其中 $v$ 和 $c$ 分别表示字母出现的次数和字母本身。

在重排字符串时，我们每次从堆顶弹出一个元素 $(v,c)$，将字母 $c$ 添加到结果字符串中，并将 $(v-1,c)$ 放入一个队列 $\mathit{\text{q}}$ 中。当队列 $\mathit{\text{q}}$ 的长度达到 $k$ 及以上时，弹出队首元素，若此时 $v$ 大于 $0$，则将队首元素重新放入堆中。重复该过程，直到堆为空。

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

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

相似题目：

• 767. 重构字符串

func rearrangeString(s string, k int) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	pq := priorityqueue.NewWith(func(a, b any) int {
		x := a.([2]int)
		y := b.([2]int)
		return y[0] - x[0]
	})

	for i := 0; i < 26; i++ {
		if cnt[i] > 0 {
			pq.Enqueue([2]int{cnt[i], i})
		}
	}

	var q [][2]int
	var ans strings.Builder

	for pq.Size() > 0 {
		p, _ := pq.Dequeue()
		pair := p.([2]int)
		pair[0]--
		ans.WriteByte(byte('a' + pair[1]))
		q = append(q, pair)

		if len(q) >= k {
			front := q[0]
			q = q[1:]
			if front[0] > 0 {
				pq.Enqueue(front)
			}
		}
	}

	if ans.Len() < len(s) {
		return ""
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

402. 移掉 K 位数字

中等1 种解法

标签：栈、贪心、字符串、单调栈

题目、示例与约束

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

 

示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。

 

提示：

• 1 <= k <= num.length <= 105
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

方法一：贪心算法 · Go 实现

思考

删除 $k$ 位后希望剩下的数字最小。相同位数的大小由最高不同位决定，因此应从高位起尽量丢掉左侧偏大的数字。

从左到右维护单调不降栈：当前位更小则弹出栈顶，相当于删掉更高位的大数，并消耗一次删除额度。删满 $k$ 位后截取剩余长度，再去掉前导零。

扫描必须自左向右：只有先删掉左侧较大数字，右侧较小数字才能进入更高位。

前置知识：两个相同位数的数字大小关系取决于第一个不同位的数的大小。

基本的思路如下：

• 从左到右遍历数组元素；
• 对于遍历到的当前元素，选择保留；
• 但可以选择性丢弃前面的相邻元素，丢弃与否取决于当前元素和前面相邻元素的大小；
• 根据前置知识可知当当前元素小于前面相邻元素时可以移除前面相邻的元素。

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

func removeKdigits(num string, k int) string {
	stk, remain := make([]byte, 0), len(num)-k
	for i := 0; i < len(num); i++ {
		n := len(stk)
		for k > 0 && n > 0 && stk[n-1] > num[i] {
			stk = stk[:n-1]
			n, k = n-1, k-1
		}
		stk = append(stk, num[i])
	}

	for i := 0; i < len(stk) && i < remain; i++ {
		if stk[i] != '0' {
			return string(stk[i:remain])
		}
	}
	return "0"
}

力扣原题 · Doocs 题解来源

409. 最长回文串

简单2 种解法

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

题目、示例与约束

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

 

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输出:1
解释：可以构造的最长回文串是"a"，它的长度是 1。

 

提示:

• 1 <= s.length <= 2000
• s 只由小写 和/或 大写英文字母组成

方法一：计数 · Go 实现

思考

回文至多一个出现奇数次的字符，其余必须成对。不必枚举排列，只需看每个字符能贡献多少对。

统计频次后，每个次数 $v$ 取 $v//2\times 2$ 累加；若总和仍小于 $|s|$，还可以再放一个字符到中心。

先取偶数对、再决定中心，保证长度最大且构造存在。

一个合法的回文字符串，最多存在一个出现奇数次数的字符，其余字符出现次数均为偶数。

因此，我们可以先遍历字符串 $s$，统计每个字符出现的次数，记录在数组或哈希表 $cnt$ 中。

然后，我们遍历 $cnt$，对于每个次数 $v$，将 $v$ 除以 2 取整，再乘以 2，累加到答案 $ans$ 中。

最后，如果答案小于字符串 $s$ 的长度，则将答案加一，返回 $ans$。

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

func longestPalindrome(s string) (ans int) {
	cnt := [128]int{}
	for _, c := range s {
		cnt[c]++
	}
	for _, v := range cnt {
		ans += v / 2 * 2
	}
	if ans < len(s) {
		ans++
	}
	return
}

方法二：位运算 + 计数 · Go 实现

思考

方法一先完整计数再求和。也可以边扫边用异或标记每个字符的奇偶，并维护奇数种类数 $\mathit{\text{cnt}}$：答案为 $n-\mathit{\text{cnt}}+1$（留一个中心）或 $n$。

少一次对频次数组的二次遍历，空间仍是字符集大小。

我们可以使用一个数组或哈希表 $odd$ 记录字符串 $s$ 中每个字符是否出现奇数次，用一个整型变量 $cnt$ 记录出现奇数次的字符个数。

遍历字符串 $s$，对于每个字符 $c$，将 $odd[c]$ 取反，即 $0\to 1$, $1\to 0$。如果 $odd[c]$ 由 $0$ 变为 $1$，则 $cnt$ 加一；如果 $odd[c]$ 由 $1$ 变为 $0$，则 $cnt$ 减一。

最后，如果 $cnt$ 大于 $0$，答案为 $n-cnt+1$，否则答案为 $n$。

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

func longestPalindrome(s string) (ans int) {
	odd := [128]int{}
	cnt := 0
	for _, c := range s {
		odd[c] ^= 1
		cnt += odd[c]
		if odd[c] == 0 {
			cnt--
		}
	}
	if cnt > 0 {
		return len(s) - cnt + 1
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

420. 强密码检验器

困难1 种解法

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

题目、示例与约束

满足以下条件的密码被认为是强密码：

• 由至少 6 个，至多 20 个字符组成。
• 包含至少 一个小写 字母，至少 一个大写 字母，和至少 一个数字 。
• 不包含连续三个重复字符 (比如 "Baaabb0" 是弱密码, 但是 "Baaba0" 是强密码)。

给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。

在一步修改操作中，你可以：

• 插入一个字符到 password ，
• 从 password 中删除一个字符，或
• 用另一个字符来替换 password 中的某个字符。

 

示例 1：

输入：password = "a"
输出：5

示例 2：

输入：password = "aA1"
输出：3

示例 3：

输入：password = "1337C0d3"
输出：0

 

提示：

• 1 <= password.length <= 50
• password 由字母、数字、点 '.' 或者感叹号 '!' 组成

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

本站根据题意与 Doocs 参考思路整理为 Go，非上游原文。按 CC BY-SA 4.0 共享。

统计缺失的字符种类和同字符连续段。短于六位优先插入；长度合格时每段需 floor(长度/3) 次替换。超长时先删除：长度模 3 为 0 的段删一位就能省一次替换，模 3 为 1 的段删两位，再按每三次删除省一次替换。剩余替换可同时补缺失字符种类。时间 O(n)，额外空间 O(1)。

func strongPasswordChecker(s string) int {
	lower, upper, digit := false, false, false
	for i := range s {
		c := s[i]
		lower = lower || (c >= 'a' && c <= 'z')
		upper = upper || (c >= 'A' && c <= 'Z')
		digit = digit || (c >= '0' && c <= '9')
	}
	missing := 0
	for _, ok := range []bool{lower, upper, digit} {
		if !ok {
			missing++
		}
	}
	n := len(s)
	if n < 6 {
		return max(6-n, missing)
	}
	replace := 0
	mods := [2]int{}
	for i := 0; i < n; {
		j := i + 1
		for j < n && s[j] == s[i] {
			j++
		}
		length := j - i
		replace += length / 3
		if length >= 3 && length%3 < 2 {
			mods[length%3]++
		}
		i = j
	}
	if n <= 20 {
		return max(replace, missing)
	}
	remove := n - 20
	remaining := remove
	used := min(remaining, mods[0])
	replace -= used
	remaining -= used
	used = min(remaining/2, mods[1])
	replace -= used
	remaining -= used * 2
	replace -= min(replace, remaining/3)
	return remove + max(replace, missing)
}

力扣原题 · Doocs 题解来源

452. 用最少数量的箭引爆气球

中等1 种解法

标签：贪心、数组、排序

题目、示例与约束

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x_start，x_end， 且满足  xstart ≤ x ≤ x_end，则该气球会被 引爆 _。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

 

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

 

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

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

思考

一支箭射穿所有覆盖该点的气球，求最少箭数。这与「用最少点刺穿所有区间」相同。

按右端升序：当前箭钉在上一个被射中气球的右端；下一个左端若超过该点，必须新射一箭并更新钉点。

钉在已选区间的右端，能覆盖尽可能多的后续气球；按右端排序保证这一贪心最优。

我们可以将所有气球按照右端点升序排序，然后从左到右遍历气球，维护当前的箭所能覆盖的最右端点 $last$，如果当前气球的左端点 $a$ 大于 $last$，说明当前箭无法覆盖当前气球，需要额外射出一支箭，那么答案加一，同时更新 $last$ 为当前气球的右端点 $b$。

遍历结束后，即可得到答案。

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

相似题目：

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

func findMinArrowShots(points [][]int) (ans int) {
	sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })
	last := -(1 << 60)
	for _, p := range points {
		a, b := p[0], p[1]
		if a > last {
			ans++
			last = b
		}
	}
	return
}

力扣原题 · Doocs 题解来源

455. 分发饼干

简单1 种解法

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

题目、示例与约束

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]_，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

 

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

 

提示：

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

 

注意：本题与 2410. 运动员和训练师的最大匹配数 题相同。

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

思考

一块饼干最多满足一个孩子，希望满足人数最多。应把小饼干留给胃口小的孩子，否则大饼干被小胃口浪费。

两数组排序后，指针扫饼干：太小就换下一块，够大则同时前进。饼干用尽则返回已满足人数。

排序后双指针保证每块饼干都尽量分给当前最容易满足的孩子。

根据题目描述，我们应该优先将饼干分配给胃口值小的孩子，这样可以尽可能满足更多的孩子。

因此，我们首先对两个数组进行排序，然后用两个指针 $i$ 和 $j$ 分别指向数组 $g$ 和 $s$ 的头部，每次比较 $g[i]$ 和 $s[j]$ 的大小：

• 如果 $s[j]<g[i]$，说明当前饼干 $s[j]$ 无法满足当前孩子 $g[i]$，我们应该将尺寸更大的饼干分配给当前孩子，因此 $j$ 应该右移一位；如果 $j$ 越界，说明无法满足当前孩子，此时成功分配的孩子数量为 $i$，直接返回即可；
• 如果 $s[j]\ge g[i]$，说明当前饼干 $s[j]$ 可以满足当前孩子 $g[i]$，我们将当前饼干分配给当前孩子，因此 $i$ 和 $j$ 都应该右移一位。

如果遍历完数组 $g$，则说明所有孩子都已经分配到饼干，则返回孩子总数即可。

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

func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	j := 0
	for i, x := range g {
		for j < len(s) && s[j] < x {
			j++
		}
		if j >= len(s) {
			return i
		}
		j++
	}
	return len(g)
}

力扣原题 · Doocs 题解来源

484. 寻找排列 🔒

中等1 种解法

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

题目、示例与约束

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

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

给定一个字符串 s ，重构字典序上最小的排列 perm 并返回它。

 

示例 1：

输入： s = "I"
输出： [1,2]
解释： [1,2] 是唯一合法的可以生成秘密签名 "I" 的特定串，数字 1 和 2 构成递增关系。

示例 2：

输入： s = "DI"
输出： [2,1,3]
解释： [2,1,3] 和 [3,1,2] 可以生成秘密签名 "DI"，
但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。

 

提示：

• 1 <= s.length <= 105
• s[i] 只会包含字符 'D' 和 'I'。

方法一：贪心 · Go 实现

思考

由 $I/D$ 串构造最小的 $1..n+1$ 排列。字典序最小应尽量保持升序，只在必须下降的地方调整。

先写成 $1,2,\dots ,n+1$，再把每一段连续 $D$ 对应的区间翻转。 $I$ 处保持原相对顺序。

翻转一段 $D$ 恰好把该区间变成递减，且不增大未涉及的前缀，因此得到最小排列。

先初始化结果数组 ans 为 [1, 2, 3, ..., n+1]。

假定某个连续 D 子数组区间为 [i, j)，那么只要翻转 ans[i: j + 1] 即可。

因此，遍历字符串 s，找出所有的连续 D 子数组区间，将其翻转。

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

func findPermutation(s string) []int {
	n := len(s)
	ans := make([]int, n+1)
	for i := range ans {
		ans[i] = i + 1
	}
	i := 0
	for i < n {
		j := i
		for ; j < n && s[j] == 'D'; j++ {
		}
		reverse(ans, i, j)
		i = max(i+1, j)
	}
	return ans
}

func reverse(arr []int, i, j int) {
	for ; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
}

力扣原题 · Doocs 题解来源

502. IPO

困难1 种解法

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

题目、示例与约束

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

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

 

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

 

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

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

思考

每次在资本允许的项目中选利润最大者，共做 $k$ 次。若每次扫描全部项目， $O(kn)$ 在 $n,k\le {10}^5$ 下偏慢。

资本门槛只升不降，因此可先按启动资本建小根堆；当前资本够格的项目再进入按利润排序的大根堆。每次从大根堆取出最大利润并更新资本。两个堆保证「刚解锁」与「最优可选」都是堆顶操作，总复杂度受排序与堆操作支配。

将每个项目放入优先队列 $q_1$ 中，按照启动资本从小到大排序。如果堆顶元素启动资本不超过当前已有的资金，则循环弹出，放入另一个优先队列 $q_2$ 中，按照纯利润从大到小排序。取出当前利润最大的项目，将其纯利润加入到当前资金中，重复上述操作 $k$ 次。

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

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
	q1 := hp2{}
	for i, c := range capital {
		heap.Push(&q1, pair{c, profits[i]})
	}
	q2 := hp{}
	for k > 0 {
		for len(q1) > 0 && q1[0].c <= w {
			heap.Push(&q2, heap.Pop(&q1).(pair).p)
		}
		if q2.Len() == 0 {
			break
		}
		w += heap.Pop(&q2).(int)
		k--
	}
	return w
}

type hp struct{ sort.IntSlice }

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

type pair struct{ c, p int }
type hp2 []pair

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

力扣原题 · Doocs 题解来源

517. 超级洗衣机

困难1 种解法

标签：贪心、数组

题目、示例与约束

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

 

示例 1：

输入：machines = [1,0,5]
输出：3
解释：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   

示例 2：

输入：machines = [0,3,0]
输出：2
解释：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     

示例 3：

输入：machines = [0,2,0]
输出：-1
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。

 

提示：

• n == machines.length
• 1 <= n <= 104
• 0 <= machines[i] <= 105

方法一：贪心 · Go 实现

思考

衣服总数若不能均分则无解。能均分时，平均每台应为 $k$。一次移动只能把一件衣服送到相邻机器，目标是最少移动次数。

将每台衣服数减去 $k$ 得到盈亏。前缀和 $s$ 表示需要净穿过当前边界的衣服件数，这些净流量必须发生。单台若超量 $x>0$，这些衣服也必须在该台各移出一次。答案取 $|s|$ 与单台超量的最大值。

如果洗衣机内的衣服总数不能被洗衣机的数量整除，那么不可能使得每台洗衣机内的衣服数量相等，直接返回 $-1$。

否则，假设洗衣机内的衣服总数为 $s$，那么最终每台洗衣机内的衣服数量都会变为 $k=s/n$。

我们定义 $a_i$ 为第 $i$ 台洗衣机内的衣服数量与 $k$ 的差值，即 $a_i=\mathit{\text{machines}}[i]-k$。若 $a_i>0$，则表示第 $i$ 台洗衣机内有多余的衣服，需要向相邻的洗衣机传递；若 $a_i<0$，则表示第 $i$ 台洗衣机内缺少衣服，需要从相邻的洗衣机获得。

我们将前 $i$ 台洗衣机的衣服数量差值之和定义为 $s_i=\sum _{j=0}^{i-1}{a}_j$，如果把前 $i$ 台洗衣机视为一组，其余的洗衣机视为另一组。那么若 $s_i$ 为正数，表示第一组洗衣机内有多余的衣服，需要向第二组洗衣机传递；若 $s_i$ 为负数，表示第一组洗衣机内缺少衣服，需要从第二组洗衣机获得。

那么有以下两种情况：

1. 两组之间的衣服，最多需要移动的次数为 $\underset{i=0}{\overset{n-1}{max}}|s_i|$；
2. 组内某一台洗衣机的衣服数量过多，需要向左右两侧移出衣服，最多需要移动的次数为 $\underset{i=0}{\overset{n-1}{max}}{a}_i$。

我们取两者的最大值即可。

时间复杂度 $O(n)$，其中 $n$ 为洗衣机的数量。空间复杂度 $O(1)$。

func findMinMoves(machines []int) (ans int) {
	n := len(machines)
	s := 0
	for _, x := range machines {
		s += x
	}
	if s%n != 0 {
		return -1
	}
	k := s / n
	s = 0
	for _, x := range machines {
		x -= k
		s += x
		ans = max(ans, max(abs(s), x))
	}
	return
}

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

力扣原题 · Doocs 题解来源

555. 分割连接字符串 🔒

中等1 种解法

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

题目、示例与约束

给定一个字符串列表 strs，你可以将这些字符串连接成一个循环字符串，对于每个字符串，你可以选择是否翻转它。在所有可能的循环字符串中，你需要分割循环字符串（这将使循环字符串变成一个常规的字符串），然后找到字典序最大的字符串。

具体来说，要找到字典序最大的字符串，你需要经历两个阶段：

1. 将所有字符串连接成一个循环字符串，你可以选择是否翻转某些字符串，并按照给定的顺序连接它们。
2. 在循环字符串的某个位置分割它，这将使循环字符串从分割点变成一个常规的字符串。

你的工作是在所有可能的常规字符串中找到字典序最大的一个。

 

示例 1:

输入: strs = ["abc","xyz"]
输出: "zyxcba"
解释: 你可以得到循环字符串 "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-"，其中 '-' 代表循环状态。 
答案字符串来自第四个循环字符串， 你可以从中间字符 'a' 分割开然后得到 "zyxcba"。

示例 2:

输入: strs = ["abc"]
输出: "cba"

 

提示:

• 1 <= strs.length <= 1000
• 1 <= strs[i].length <= 1000
• 1 <= sum(strs[i].length) <= 1000
• strs[i] 只包含小写英文字母

方法一：贪心 · Go 实现

思考

字符串可先各自翻转，再选定一个切开的位置作为起点拼成环。暴力枚举所有翻转组合与切点过多。

先把每个串改成它与其反转的字典序较大者，环上其余部分便已尽可能大。再枚举切在哪一个串、以及该串的切点，比较「原向切开」与「整段再反转切开」两种，取全局最大。

我们先遍历字符串数组 strs，对于每个字符串 $s$，如果 $s$ 的反转字符串 $t$ 比 $s$ 大，那么我们就将 $s$ 替换为 $t$。

然后我们再枚举字符串数组 strs 的每个位置 $i$ 作为分割点，将字符串数组 strs 拆成两部分，分别为 $strs[i+1:]$ 和 $strs[:i]$，然后将这两部分拼接起来，得到一个新的字符串 $t$。接下来，我们枚举当前字符串 $strs[i]$ 的每个位置 $j$，其后缀部分为 $a=strs[i][j:]$，前缀部分为 $b=strs[i][:j]$，那么我们可以将 $a$, $t$ 和 $b$ 拼接起来，得到一个新的字符串 $cur$，如果 $cur$ 比当前答案大，那么我们就更新答案。这是将 $strs[i]$ 翻转后的情况，我们还需要考虑 $strs[i]$ 不翻转的情况，即将 $a$, $t$ 和 $b$ 的顺序反过来拼接，得到一个新的字符串 $cur$，如果 $cur$ 比当前答案大，那么我们就更新答案。

最后，我们返回答案即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为字符串数组 strs 的长度。

func splitLoopedString(strs []string) (ans string) {
	for i, s := range strs {
		t := reverse(s)
		if s < t {
			strs[i] = t
		}
	}
	for i, s := range strs {
		sb := &strings.Builder{}
		for _, w := range strs[i+1:] {
			sb.WriteString(w)
		}
		for _, w := range strs[:i] {
			sb.WriteString(w)
		}
		t := sb.String()
		for j := 0; j < len(s); j++ {
			a, b := s[j:], s[0:j]
			cur := a + t + b
			if ans < cur {
				ans = cur
			}
			cur = reverse(b) + t + reverse(a)
			if ans < cur {
				ans = cur
			}
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

561. 数组拆分

简单1 种解法

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

题目、示例与约束

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

 

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

 

提示：

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

方法一：排序 · Go 实现

思考

两两配对后取每对较小值之和，要让这个和最大。较小值被浪费的是较大的那个数，因此应让较大值尽量小——即与接近的数配对。

排序后相邻两项组成一对， $a_1+a_3+\cdots$ 即为最优。证明上，任何交叉配对都可以调整成相邻配对且不变更差。

对于一个数对 $(a,b)$，我们不妨设 $a\le b$，那么 $min(a,b)=a$。为了使得总和尽可能大，我们取的 $b$ 应该与 $a$ 尽可能接近，这样可以保留更大的数。

因此，我们可以对数组 $nums$ 进行排序，然后将相邻的两个数分为一组，取每组的第一个数相加即可。

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

func arrayPairSum(nums []int) (ans int) {
	sort.Ints(nums)
	for i := 0; i < len(nums); i += 2 {
		ans += nums[i]
	}
	return
}

力扣原题 · Doocs 题解来源

581. 最短无序连续子数组

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

 

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

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

示例 3：

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

 

提示：

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

 

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

方法一：排序 · Go 实现

思考

最短无序子数组排序后应使整个数组有序。把数组排序再与原数组比较，两端第一个不同的位置就是要排序的区间。

$n\le {10}^4$，排序可以接受。若两端从未错位则数组已有序，长度为 $0$。

我们可以先对数组进行排序，然后比较排序后的数组和原数组，找到最左边和最右边不相等的位置，它们之间的长度就是我们要找的最短无序连续子数组的长度。

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

func findUnsortedSubarray(nums []int) int {
	arr := make([]int, len(nums))
	copy(arr, nums)
	sort.Ints(arr)
	l, r := 0, len(arr)-1
	for l <= r && nums[l] == arr[l] {
		l++
	}
	for l <= r && nums[r] == arr[r] {
		r--
	}
	return r - l + 1
}

方法二：维护左侧最大值和右侧最小值 · Go 实现

思考

排序多花了对数因子。从左扫，一旦当前值小于左侧最大值，它就必须落入待排序区间，右端点持续更新；从右扫则用右侧最小值更新左端点。

两端初值为 $-1$，若右端从未更新则返回 $0$。线性两遍，空间常数。

我们可以从左到右遍历数组，维护一个最大值 $mx$，如果当前值小于 $mx$，说明当前值不在正确的位置上，我们更新右边界 $r$ 为当前位置。同理，我们可以从右到左遍历数组，维护一个最小值 $mi$，如果当前值大于 $mi$，说明当前值不在正确的位置上，我们更新左边界 $l$ 为当前位置。在初始化时，我们将 $l$ 和 $r$ 都初始化为 $-1$，如果 $l$ 和 $r$ 都没有被更新，说明数组已经有序，返回 $0$，否则返回 $r-l+1$。

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

func findUnsortedSubarray(nums []int) int {
	const inf = 1 << 30
	n := len(nums)
	l, r := -1, -1
	mi, mx := inf, -inf
	for i, x := range nums {
		if mx > x {
			r = i
		} else {
			mx = x
		}
		if mi < nums[n-i-1] {
			l = n - i - 1
		} else {
			mi = nums[n-i-1]
		}
	}
	if r == -1 {
		return 0
	}
	return r - l + 1
}

力扣原题 · Doocs 题解来源

605. 种花问题

简单1 种解法

标签：贪心、数组

题目、示例与约束

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

 

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

 

提示：

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] 为 0 或 1
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

方法一：贪心 · Go 实现

思考

花不能与已有花相邻，且需判断能否放下 $n$ 朵。枚举所有放置子集时，花坛长度可达 $2\times {10}^4$，不可行。

能放则尽早放不会妨碍后面更多位置。两端补 $0$ 后，连续三位和为 $0$ 即可种下；种完看剩余 $n$ 是否非正。

我们直接遍历数组 $flowerbed$，对于每个位置 $i$，如果 $flowerbed[i]=0$，并且其左右相邻位置都为 $0$，则我们可以在该位置种花，否则不能。最后我们统计可以种下的花的数量，如果其不小于 $n$，则返回 $true$，否则返回 $false$。

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

func canPlaceFlowers(flowerbed []int, n int) bool {
	m := len(flowerbed)
	for i, v := range flowerbed {
		l, r := 0, 0
		if i > 0 {
			l = flowerbed[i-1]
		}
		if i < m-1 {
			r = flowerbed[i+1]
		}
		if l+v+r == 0 {
			flowerbed[i] = 1
			n--
		}
	}
	return n <= 0
}

力扣原题 · Doocs 题解来源

611. 有效三角形的个数

中等1 种解法

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

题目、示例与约束

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

 

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

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

 

提示:

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

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

思考

三重循环枚举边在 $n\le {10}^3$ 时尚可，但可压到 $O(n^2\log n)$。排序后 $a\le b\le c$ 只需 $a+b>c$。

固定较小两边 $i,j$，在右侧二分第一处 $\ge nums[i]+nums[j]$ 的位置，其间下标都可作为第三边。

一个有效三角形需要满足：任意两边之和大于第三边。即：

$$\begin{array}{}\text{(1)}& a+b>c\end{array}$$$$\begin{array}{}\text{(2)}& a+c>b\end{array}$$$$\begin{array}{}\text{(3)}& b+c>a\end{array}$$

如果我们将边按从小到大顺序排列，即 $a\le b\le c$，那么显然 (2)(3) 成立，我们只需要确保 (1) 也成立，就可以形成一个有效三角形。

我们在 $[0,n-3]$ 范围内枚举 i，在 $[i+1,n-2]$ 范围内枚举 j，在 $[j+1,n-1]$ 范围内进行二分查找，找出第一个大于等于 $nums[i]+nums[j]$ 的下标 left，那么在 $[j+1,left-1]$ 范围内的 k 满足条件，将其累加到结果 $\mathit{\text{ans}}$。

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

func triangleNumber(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	ans := 0
	for i := 0; i < n-2; i++ {
		for j := i + 1; j < n-1; j++ {
			sum := nums[i] + nums[j]
			k := sort.SearchInts(nums[j+1:], sum) + j + 1 - 1
			if k > j {
				ans += k - j
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

621. 任务调度器

中等1 种解法

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

题目、示例与约束

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔 。

 

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

解释：

在完成任务 A 之后，你必须等待两个间隔。对任务 B 来说也是一样。在第 3 个间隔，A 和 B 都不能完成，所以你需要待命。在第 4 个间隔，由于已经经过了 2 个间隔，你可以再次执行 A 任务。

 

示例 2：

输入：tasks = ["A","C","A","B","D","B"], n = 1

输出：6

解释：一种可能的序列是：A -> B -> C -> D -> A -> B。

由于冷却间隔为 1，你可以在完成另一个任务后重复执行这个任务。

示例 3：

输入：tasks = ["A","A","A","B","B","B"], n = 3

输出：10

解释：一种可能的序列为：A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B。

只有两种任务类型，A 和 B，需要被 3 个间隔分割。这导致重复执行这些任务的间隔当中有两次待命状态。

 

提示：

• 1 <= tasks.length <= 104
• tasks[i] 是大写英文字母
• 0 <= n <= 100

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

思考

相同任务之间至少间隔 $n$，直接模拟时间轴在任务数较大时偏慢，且冷却空档要显式填。

次数最多的任务决定「框架」： $(x-1)$ 个完整间隔加上最后一批 $s$ 个并列最多者。若任务总数更大，空档会被其余任务填满，故答案取 $max(m,(x-1)(n+1)+s)$。

不妨设 $m$ 是任务的个数，统计每种任务出现的次数，记录在数组 cnt 中。

假设出现次数最多的任务为 A，出现次数为 $x$，则至少需要 $(x-1)\times (n+1)+1$ 个时间单位才能安排完所有任务。如果出现次数最多的任务有 $s$ 个，则需要再加上出现次数最多的任务的个数。

答案是 $max((x-1)\times (n+1)+s,m)$。

时间复杂度 $O(m+|\mathrm{\Sigma }|)$。其中 $|\mathrm{\Sigma }|$ 是任务的种类数。

func leastInterval(tasks []byte, n int) int {
	cnt := make([]int, 26)
	x := 0
	for _, c := range tasks {
		c -= 'A'
		cnt[c]++
		x = max(x, cnt[c])
	}
	s := 0
	for _, v := range cnt {
		if v == x {
			s++
		}
	}
	return max(len(tasks), (x-1)*(n+1)+s)
}

力扣原题 · Doocs 题解来源

624. 数组列表中的最大距离

中等1 种解法

标签：贪心、数组

题目、示例与约束

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

示例 2：

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

 

提示：

• m == arrays.length
• 2 <= m <= 105
• 1 <= arrays[i].length <= 500
• -104 <= arrays[i][j] <= 104
• arrays[i] 以 升序 排序。
• 所有数组中最多有 105 个整数。

 

方法一：维护最大值和最小值 · Go 实现

思考

距离取自不同数组的两端值。若枚举数组对再取 $max-min$，数组个数可达 ${10}^4$ 时为平方级。

最大距离只可能是「当前数组一端」与「此前全局另一端」。从第二个数组起，先与已维护的 $\mathit{\text{mi}},\mathit{\text{mx}}$ 求距离，再把本数组两端并入全局，保证两端不来自同一数组。

我们注意到，最大距离一定是两个数组中的一个最大值和另一个最小值之间的距离。因此，我们可以维护两个变量 $\mathit{\text{mi}}$ 和 $\mathit{\text{mx}}$，分别表示已经遍历过的数组中的最小值和最大值。初始时 $\mathit{\text{mi}}$ 和 $\mathit{\text{mx}}$ 分别为第一个数组的第一个元素和最后一个元素。

接下来，我们从第二个数组开始遍历，对于每个数组，我们首先计算当前数组的第一个元素和 $\mathit{\text{mx}}$ 之间的距离，以及当前数组的最后一个元素和 $\mathit{\text{mi}}$ 之间的距离，然后更新最大距离。同时，我们更新 $\mathit{\text{mi}}=min(\mathit{\text{mi}},\mathit{\text{arr}}[0])$ 和 $\mathit{\text{mx}}=max(\mathit{\text{mx}},\mathit{\text{arr}}[\mathit{\text{size}}-1])$。

遍历结束后，即可得到最大距离。

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

func maxDistance(arrays [][]int) (ans int) {
	mi, mx := arrays[0][0], arrays[0][len(arrays[0])-1]
	for _, arr := range arrays[1:] {
		a, b := abs(arr[0]-mx), abs(arr[len(arr)-1]-mi)
		ans = max(ans, max(a, b))
		mi = min(mi, arr[0])
		mx = max(mx, arr[len(arr)-1])
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

625. 最小因式分解 🔒

中等1 种解法

标签：贪心、数学、质因数分解

题目、示例与约束

给定一个正整数 num，找出最小的正整数 x 使得 x 的所有数位相乘恰好等于 num。

如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。

 

示例 1：

输入：num = 48
输出：68

示例 2：

输入：num = 15
输出：35

 

提示：

• 1 <= num <= 231 - 1

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

思考

要把 $num$ 拆成若干个 $2..9$ 的乘积，并使拼成的整数最小。拆法很多，穷举位数不可取。

位数越少、高位越小则数越小，故从 $9$ 往 $2$ 尽量整除，把因子从低位写入。若最后剩 $num>1$ 或溢出 $32$ 位有符号范围，则无法构成。

我们先判断 $num$ 是否小于 $2$，如果是，直接返回 $num$。然后从 $9$ 开始，尽可能多地将数字分解为 $9$，然后分解为 $8$，以此类推，直到分解为 $2$。如果最后剩下的数字不是 $1$，或者结果超过了 $2^{31}-1$，则返回 $0$。否则，我们返回结果。

注意，分解后的数字，应该依次填充到结果的个位、十位、百位、千位……上，因此我们需要维护一个变量 $mul$，表示当前的位数。

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

func smallestFactorization(num int) int {
	if num < 2 {
		return num
	}
	ans, mul := 0, 1
	for i := 9; i >= 2; i-- {
		if num%i == 0 {
			for num%i == 0 {
				num /= i
				ans = mul*i + ans
				mul *= 10
			}
		}
	}
	if num < 2 && ans <= math.MaxInt32 {
		return ans
	}
	return 0
}

力扣原题 · Doocs 题解来源

630. 课程表 III

困难1 种解法

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

题目、示例与约束

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

 

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

 

提示:

• 1 <= courses.length <= 104
• 1 <= durationi, lastDayi <= 104

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

思考

每门课有时长与截止日期，求最多能上几门。按组合搜索在课程数 $n\le {10}^4$ 时不可行。

按截止时间排序后尽量都上；若当前总时长超过截止，就丢掉已选中时长最大的一门（大根堆），为后面更紧的课腾出时间。堆中剩余即最优门数。

我们可以按照课程的结束时间进行升序排序，每次选择结束时间最早的课程进行上课。

如果已选择的课程的总时间 $s$ 超过了当前课程的结束时间 $last$，那么我们就将此前选择的课程中耗时最长的课程去掉，直到能够满足当前课程的结束时间为止。这里我们使用一个优先队列（大根堆） $pq$ 来维护当前已经选择的课程的耗时，每次我们都从优先队列中取出耗时最长的课程进行去除。

最后，优先队列中的元素个数即为我们能够选择的课程数目。

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

func scheduleCourse(courses [][]int) int {
	sort.Slice(courses, func(i, j int) bool { return courses[i][1] < courses[j][1] })
	pq := &hp{}
	s := 0
	for _, e := range courses {
		duration, last := e[0], e[1]
		s += duration
		pq.push(duration)
		for s > last {
			s -= pq.pop()
		}
	}
	return pq.Len()
}

type hp struct{ sort.IntSlice }

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

力扣原题 · Doocs 题解来源

632. 最小区间

困难1 种解法

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

题目、示例与约束

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

 

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

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

 

提示：

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -105 <= nums[i][j] <= 105
• nums[i] 按非递减顺序排列

 

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

思考

要从 $k$ 个有序列表各取至少一个数，使覆盖区间最短。枚举每个列表的下标组合在总长度较大时不可行。

把所有 $(\mathrm{值},\mathrm{组}\mathrm{号})$ 排成一条有序序列后，问题变成最短窗口恰好覆盖 $k$ 个组。右端扩张、左端在组数仍为 $k$ 时收缩，用计数表维护窗口内的组。

我们将每个数字 $x$ 及其所在的组 $i$，构成数据项 $(x,i)$，存放在一个新的数组 $t$ 中，然后对 $t$ 按照数字的大小进行排序（类似于将多个有序数组合并成一个新的有序数组）。

接下来，我们遍历 $t$ 中的每个数据项，只看其中数字所在的组，用哈希表记录滑动窗口内的数字出现的组，如果组数为 $k$，说明当前窗口满足题目要求，此时算出窗口的起始和结束位置，更新答案。

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

func smallestRange(nums [][]int) []int {
	t := [][]int{}
	for i, x := range nums {
		for _, v := range x {
			t = append(t, []int{v, i})
		}
	}
	sort.Slice(t, func(i, j int) bool { return t[i][0] < t[j][0] })
	ans := []int{-1000000, 1000000}
	j := 0
	cnt := map[int]int{}
	for _, x := range t {
		b, v := x[0], x[1]
		cnt[v]++
		for len(cnt) == len(nums) {
			a, w := t[j][0], t[j][1]
			x := b - a - (ans[1] - ans[0])
			if x < 0 || (x == 0 && a < ans[0]) {
				ans[0], ans[1] = a, b
			}
			cnt[w]--
			if cnt[w] == 0 {
				delete(cnt, w)
			}
			j++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源