10.1 贪心策略

约 24707 字大约 82 分钟

2025-04-16

有时候，很难一眼看出一道题是贪心还是 DP。

前言

为方便大家练习，我把比较套路的贪心题目放在前面，更灵活的思维题和构造题放在后面。每个小节的题目均按照从易到难的顺序排列。

如果做题时没有思路，推荐看看本文第五章的「思考清单」。

有两种基本贪心策略：

从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。在此基础上，衍生出了反悔贪心。
从最左/最右开始贪心，思考第一个数/最后一个数的贪心策略，把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。

10.1.1 从最小/最大开始贪心

优先考虑最小/最大的数，从小到大/从大到小贪心。

如果答案与数组元素顺序无关，一般需要排序。排序后，可以遍历计算。

3074. 重新分装苹果
给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的最小数量。注意，同一个包裹中的苹果可以分装到不同的箱子中。
示例 1：
输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。
示例 2：
输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。
提示
思路：从最大开始贪心。 要求最少的箱子使用量，并且苹果是可以分装的，那么只需要求出苹果的总重，然后依次从大到小选择箱子，直到满足苹果总重即可。
```
class Solution:
def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
    total = sum(apple) # O(n)
    capacity.sort(reverse=True) # O(mlogm)
    cur_capacity = 0
    for i, c in enumerate(capacity): # O(m)
        cur_capacity += c
        if cur_capacity >= total:
            return i + 1
```
时间复杂度： $O(n+mlogm)$ ，其中 n 为 apple 的长度，m 为 capacity 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
2279. 装满石头的背包的最大数量
现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整 additionalRocks ，表示你可以放置的额外石头数量，石头可以往任意背包中放置。请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的最大数量。
示例 1：
输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。
示例 2：
输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3
解释：
8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。
提示
思路：从最小开始贪心。 要求最多能装满多少背包，可以先求出背包的空余容量，然后从小到大排序，把额外石头依次装满背包，直到石头用完，这时装满的背包数量就是所求。
```
class Solution:
def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
    free = [c - r for c, r in zip(capacity, rocks)] # O(n)
    free.sort() # O(nlogn)
    for i, f in enumerate(free): # O(n)
        additionalRocks -= f
        if additionalRocks == 0:
            return i + 1
        elif additionalRocks < 0:
            return i
    return len(capacity)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 capacity 的长度。
空间复杂度： $O(n)$ ，忽略排序的栈开销。
1833. 雪糕的最大数量
夏日炎炎，小男孩 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 。
提示
思路：从最小开始贪心。 要求买更多数量的雪糕，因此我们要尽可能买便宜的（小布丁而不是巧乐兹），把雪糕价格从小到大排序，然后购买即可。
```
class Solution:
def maxIceCream(self, costs: List[int], coins: int) -> int:
    costs.sort() # O(nlogn)
    for i, c in enumerate(costs): # O(n)
        coins -= c
        if coins == 0:
            return i + 1
        elif coins < 0:
            return i
    return len(costs)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 costs 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
1005. K 次取反后最大化的数组和
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：选择某个下标 i 并将 nums[i] 替换为 -nums[i] 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后，返回数组可能的最大和。
示例 1：
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
示例 2：
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
提示
思路：从最小开始贪心。 要求数组的和最大，同时数组有正有负，那么我们可以先把数组排序，然后把前面的负数翻转，当负数全部翻转完毕，此时如果还有k，因为可以多次选择同一个下标，所以可以按照奇偶来分类，如果k是奇数，那么翻转最小的正数（提前存储），如果是偶数，不需要翻转。还有一种情况，那就是 nums 中全部是负数，且 k > len(nums) ，此时因为超过for循环，因此在循环外需要额外判断一次。（感觉这里可以优化一下）
```
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
    nums.sort() # O(nlogn)
    min_value = float('inf')
    for i, num in enumerate(nums): # O(n)
        if num < 0:
            min_value = min(-num, min_value)
            nums[i] = -num
            k -= 1
        elif num >= 0:
            min_value = min(num, min_value)
            if k % 2 == 0:
                return sum(nums)
            else:
                return sum(nums) - 2 * min_value
        if k == 0:
            return sum(nums)
    return sum(nums) - 2 * min_value if k and k % 2 else sum(nums)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
重要
sum(nums) 虽然是 $O(n)$ ，但它只在满足条件时被执行一次，而且之后整个函数就 return，循环立刻结束。所以，最多只会执行一次 $O(n)$ 的 sum(nums)。所以，循环内部总体时间复杂度是： $O(n) + O(n) = O(n)$ ，而不是 $O(n^2)$ 。
1481. 不同整数的最少数目
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
示例 1：
输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数
示例 2：
输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
提示
思路：从最小开始贪心。 要求数组中的元素种类最少，我们需要先移除数量较少的数字类别，可以初始化一个计数器，然后把计数器按照 value 的值从小到大排序，先移走小的类别，最后如果数组全部被移走，返回0。
```
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
    from collections import Counter

    cnt_arr = sorted(Counter(arr).values()) # O(n) + O(mlogm)
    for i, num in enumerate(cnt_arr): # O(m)
        k -= num
        if k >= 0:
            continue
        if k < 0:
            return len(cnt_arr) - i
    return 0
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(n)$ ，忽略排序的栈开销。
重要
m 为 nums 的种类数，因为 m 不会超过 n，故 $O(n) + O(mlogm)$ 可简化为 $O(nlogn)$ 。
1403. 非递增顺序的最小子序列
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。如果存在多个解决方案，只需返回长度最小的子序列。如果仍然有多个解决方案，则返回元素之和最大的子序列。与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。注意，题目数据保证满足所有约束条件的解决方案是唯一的。同时，返回的答案应当按非递增顺序排列。
示例 1：
输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
示例 2：
输入：nums = [4,4,7,6,7]
输出：[7,7,6]
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。
提示
思路：从最大开始贪心。 要求数组的子序列的数量尽可能少，子序列的和尽可能大，因此可以考虑从最大值开始选取子序列，这可以通过从大到小排序实现。为了方便书写代码，我们可以使用一个数学技巧：只要选取的子序列之和大于总数组之和的一半即可满足题目要求。
```
class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:

    sum_nums = sum(nums) # O(n)
    nums.sort(reverse=True) # O(nlogn)
    cur = 0
    for i, num in enumerate(nums): # O(n)
        cur += num
        if cur > sum_nums / 2:
            return nums[:i + 1]
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(n)$ ，忽略排序的栈开销。
重要
nums[:i + 1]创建了一个新列表，包含前 k 个元素（最坏 $O(n)$ ）
3010. 将数组分成最小总代价的子数组 I
给你一个长度为 n 的整数数组 nums 。一个数组的代价是它的第一个元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。你需要将 nums 分成 3 个连续且没有交集的子数组。请你返回这些子数组的最小代价总和。
示例 1：
输入：nums = [1,2,3,12]
输出：6
解释：最佳分割成 3 个子数组的方案是：[1] ，[2] 和 [3,12] ，总代价为 1 + 2 + 3 = 6 。
其他得到 3 个子数组的方案是：
- [1] ，[2,3] 和 [12] ，总代价是 1 + 2 + 12 = 15 。
- [1,2] ，[3] 和 [12] ，总代价是 1 + 3 + 12 = 16 。
示例 2：
输入：nums = [5,4,3]
输出：12
解释：最佳分割成 3 个子数组的方案是：[5] ，[4] 和 [3] ，总代价为 5 + 4 + 3 = 12 。
12 是所有分割方案里的最小总代价。
示例 3：
输入：nums = [10,3,1,1]
输出：12
解释：最佳分割成 3 个子数组的方案是：[10,3] ，[1] 和 [1] ，总代价为 10 + 1 + 1 = 12 。
12 是所有分割方案里的最小总代价。
提示
思路：从最小开始贪心。 要求代价最小，那么只需要求出三个最小的值作为子数组起始元素即可，注意是子数组而不是子序列，因此数组的第一个元素必定选取，也就转换成 nums[0] + 数组最小的2个元素。可以把 nums[1:] 进行从小到大排序，选取 nums[0] 和 nums[1] 即可。
```
class Solution:
def minimumCost(self, nums: List[int]) -> int:
    res = nums[0]
    nums = sorted(nums[1:]) # O(nlogn)
    res += nums[0] + nums[1]
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(n)$ ，忽略排序的栈开销。
重要
nums[1:] 创建了一个新列表，包含后 n - 1 个元素
1338. 数组大小减半
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。返回至少能删除数组中的一半整数的整数集合的最小大小。
示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。
提示
思路：从最大开始贪心。 要求所需删除的集合长度最小，那么需要尽可能地选择元素更多的数字类别，先把元素类别按照从大到小排序，然后选取足够大于数组长度一半的即可。这题与第 6 题类似。
```
class Solution:
def minSetSize(self, arr: List[int]) -> int:
    from collections import Counter
    cnt = Counter(arr)
    arr_class = sorted(cnt.values(), reverse=True) # O(nlogn)
    cur = 0
    for i, num in enumerate(arr_class): # O(n)
        cur += num
        if cur >= len(arr) / 2:
            return i + 1
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(n)$ ，忽略排序的栈开销。
1710. 卡车上的最大单元数
请你将一些箱子装在一辆卡车上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：numberOfBoxesi 是类型 i 的箱子的数量。numberOfUnitsPerBoxi 是类型 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 个位置），将容量从大到小排序，然后依次选择将 truckSize 用完即可。
```
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
    boxTypes.sort(key = lambda x: x[1], reverse=True) # o(nlogn)
    res = 0
    for i, box in enumerate(boxTypes): # o(n)
        if box[0] >= truckSize:
            return res + truckSize * box[1]
        truckSize -= box[0]
        res += box[0] * box[1]
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 boxTypes 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
3075. 幸福值最大化的选择方案
给你一个长度为 n 的数组 happiness ，以及一个正整数 k 。n 个孩子站成一队，其中第 i 个孩子的幸福值是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。在每一轮选择一个孩子时，所有尚未被选中的孩子的幸福值将减少 1 。注意，幸福值不能变成负数，且只有在它是正数的情况下才会减少。选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的最大值。
示例 1：
输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
  所选孩子的幸福值之和为 3 + 1 = 4 。
示例 2：
输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
  所选孩子的幸福值之和为 1 + 0 = 1 。
示例 3：
输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
  所选孩子的幸福值之和为 5 。
提示
思路：从最大开始贪心。 要求幸福值之和最大，那么可以把幸福值从大到小排序，然后依次选择k个，因为每一回合未选中的孩子的幸福值会 - 1 ，这可以用 值 - 下标 表示惩罚。
```
class Solution:
def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
    happiness.sort(reverse=True) # o(nlogn)
    res = 0
    for i, x in enumerate(happiness[:k]): # o(n)
        if x <= i:
            break
        res += x - i
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 happiness 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
2554. 从一个范围内选择最多整数 I
给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：被选择整数的范围是 [1, n] 。每个整数至多选择一次。被选择整数不能在数组 banned 中。被选择整数的和不超过 maxSum 。请你返回按照上述规则最多可以选择的整数数目。
示例 1：
输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：你可以选择整数 2 和 4 。
2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
示例 2：
输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
解释：按照上述规则无法选择任何整数。
示例 3：
输入：banned = [11], n = 7, maxSum = 50
输出：7
解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。
提示
思路：从最小开始贪心。 要求数目尽可能地多，那么需要从小数开始选取，限制在1~n之间，且和不能超过 maxSum，且不能使用banned，依题意暴力即可。
```
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
    num_class = 0
    cur_sum = 0
    banned_set = set(banned) # O(m)
    for num in range(1, n + 1): # O(n)
        if num in banned_set:
            continue
        if cur_sum + num > maxSum:
            return num_class
        cur_sum += num
        num_class += 1
    return num_class
```
时间复杂度： $O(n + m)$ ，其中 n 为 happiness 的长度，m 为 banned 的长度。
空间复杂度： $O(m)$ 。
重要
if num in banned: 与 if num in banned_set: ：如果 banned 是一个 list（比如 [2, 4, 6]），Python 每次都得从头到尾一个个比，最坏情况时间复杂度是 O(k)，其中 k 是 banned 的长度。如果你把它换成一个 set（比如 {2, 4, 6}），那么查找的时间复杂度是 O(1)，几乎是瞬间查出有没有的。set 的底层结构，和字典（dict）几乎是一样的，都是基于哈希表（Hash Table）实现的。
2126. 摧毁小行星
给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。你可以按任意顺序重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量大于等于小行星的质量，那么小行星被摧毁，并且行星会获得这颗小行星的质量。否则，行星将被摧毁。如果所有小行星都能被摧毁，请返回 true ，否则返回 false 。
示例 1：
输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
  所有小行星都被摧毁。
示例 2：
输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。
提示
思路：从最小开始贪心。 要求所有小行星都被摧毁，类似大鱼吃小鱼，只需要让行星从小到大开始吃即可。
```
class Solution:
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
    asteroids.sort() # O(nlogn)
    for i, x in enumerate(asteroids): # O(n)
        if mass < x:
            return False
        mass += x
    return True
```
时间复杂度： $O(nlogn)$ ，其中 n 为 asteroids 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
2587. 重排数组以得到最大前缀分数
给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按任意顺序重排（包括给定顺序）。令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。nums 的分数是 prefix 数组中正整数的个数。返回可以得到的最大分数。
示例 1：
输入：nums = [2,-1,0,1,-3,3,-3]
输出：6
解释：数组重排为 nums = [2,3,1,-1,-3,0,-3] 。
prefix = [2,5,6,5,2,2,-1] ，分数为 6 。
可以证明 6 是能够得到的最大分数。
示例 2：
输入：nums = [-2,-3,0]
输出：0
解释：不管怎么重排数组得到的分数都是 0 。
提示
思路：从最大开始贪心。 要求正整数的个数尽可能地多，那么需要把大的正数往前放，这样后面的每个数都会加上这个大的正数，因此我们需要把 nums 从大到小排序。
```
class Solution:
def maxScore(self, nums: List[int]) -> int:
    nums.sort(reverse=True) # O(nlogn)
    cur = 0
    for i, num in enumerate(nums): # O(n)
        if cur + num <= 0:
            return i
        cur += num
    return len(nums)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
976. 三角形的最大周长
给定由一些正数（代表长度）组成的数组 nums ，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。
示例 1：
输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形:1 2 2。
示例 2：
输入：nums = [1,2,1,10]
输出：0
解释：
你不能用边长 1,1,2 来组成三角形。
不能用边长 1,1,10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。
提示
思路：从最大开始贪心。 要求三角形的周长尽可能地大，可以先把 nums 从大到小排序，因为已经有了顺序，三角形的判定条件可以从任意两边之和大于第三边简化为 b + c > a （a是最大边），如果不满足，那么b和c后面的元素必定不会满足，所以需要移动a到b的位置，而b和c也需要顺带往后移一位。
```
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
    nums.sort(reverse=True) # O(nlogn)
    for i in range(len(nums) - 2): # O(nl)
        if nums[i + 1] + nums[i + 2] > nums[i]:
            return nums[i + 1] + nums[i + 2] + nums[i]
    return 0
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
1561. 你可以获得的最大硬币数目
有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：每一轮中，你将会选出任意 3 堆硬币（不一定连续）。Alice 将会取走硬币数量最多的那一堆。你将会取走硬币数量第二多的那一堆。Bob 将会取走最后一堆。重复这个过程，直到没有更多硬币。给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。返回你可以获得的最大硬币数目。
示例 1：
输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2：
输入：piles = [2,4,5]
输出：4
示例 3：
输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18
提示
思路：从最大开始贪心。 要求我们获得的钱最多，按照Alice、我、Bob的顺序，Alice 一定会拿走最大的，那么我们需要紧跟拿第二大的，同时 Bob 每次取走最少的钱（可以简化为删除最小的那几份钱，直接把 Bob 踢掉），按照从大到小的顺序排列，Alice和我，你拿一次我拿一次，你拿一次我拿一次。
```
class Solution:
def maxCoins(self, piles: List[int]) -> int:
    piles.sort(reverse=True) # O(nlogn)
    n = len(piles)
    round = n // 3
    res = 0
    for i in range(n - round):
        if i % 2 == 1:
            res += piles[i]
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 piles 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
3462. 提取至多 K 个元素的最大总和
给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：从 grid 的第 i 行提取的元素数量不超过 limits[i] 。返回最大总和。
示例 1：
输入：grid = [[1,2],[3,4]], limits = [1,2], k = 2
输出：7
解释：
从第 2 行提取至多 2 个元素，取出 4 和 3 。
至多提取 2 个元素时的最大总和 4 + 3 = 7 。
示例 2：
输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3
输出：21
解释：
从第 1 行提取至多 2 个元素，取出 7 。
从第 2 行提取至多 2 个元素，取出 8 和 6 。
至多提取 3 个元素时的最大总和 7 + 8 + 6 = 21 。
提示
思路：从最大开始贪心。 要求最大总和，并且每一行有限制数量 limits ，那么可以先把第 i 行的限制数量个数 limits[i] 的最大值选出来，加入新列表 temp ，最后选出新列表 temp 的最大的 k 个求和即可。
```
class Solution:
def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
    temp = []
    for i, row in enumerate(grid): # O(n)
        row.sort(reverse=True) # O(mlogm)
        temp.extend(row[:limits[i]]) # O(m)
    temp.sort(reverse=True) # O(nmlognm)
    return sum(temp[:k]) # O(k)
```
时间复杂度： $O(nmlognm)$ ，其中 n 为 grid 的行数，m 为 grid 的列数。
空间复杂度： $O(nm)$ ，忽略排序的栈开销。
重要
temp.extend(row[:limits[i]])：每行最多 extend m 个 → 总共是 O(n * m)，将 temp 排序，成为时间复杂度最大项；temp 是一个新列表，最多存储 n * m 个数。
3301. 高度互不相同的最大塔高和
给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的最大高度。你的任务是给每一座塔分别设置一个高度，使得：第 i 座塔的高度是一个正整数，且不超过 maximumHeight[i] 。所有塔的高度互不相同。请你返回设置完所有塔的高度后，可以达到的最大总高度。如果没有合法的设置，返回 -1 。
示例 1：
输入：maximumHeight = [2,3,4,3]
输出：10
解释：
我们可以将塔的高度设置为：[1, 2, 4, 3] 。
示例 2：
输入：maximumHeight = [15,10]
输出：25
解释：
我们可以将塔的高度设置为：[15, 10] 。
示例 3：
输入：maximumHeight = [2,2,1]
输出：-1
解释：
无法设置塔的高度为正整数且高度互不相同。
提示
思路：从最大开始贪心。 要求最大总高度，可以先把 maximumHeight 从大到小排序，如果遇到重复元素，那么当前值 - 1 ，最后求 sum 即可。
```
class Solution:
def maximumTotalSum(self, maximumHeight: List[int]) -> int:
    maximumHeight.sort(reverse=True) # O(nlogn)
    for i in range(1, len(maximumHeight)): # O(n)
        maximumHeight[i] = min(maximumHeight[i], maximumHeight[i - 1] - 1)
        if maximumHeight[i] == 0:
            return -1
    return sum(maximumHeight)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 maximumHeight 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
945. 使数组唯一的最小增量
给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。生成的测试用例保证答案在 32 位整数范围内。
示例 1：
输入：nums = [1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
示例 2：
输入：nums = [3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
提示
思路：从最小开始贪心。 要求每个数组的值变成唯一的，这题思路和 17 类似，先把 nums 从小到大排序，然后遍历 nums ，如果和前一个元素重复就 + 1。
```
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
    nums.sort() # O(nlogn)
    res = 0
    for i in range(1, len(nums)): # O(n)
        res += max(nums[i], nums[i - 1] + 1) - nums[i]
        nums[i] = max(nums[i], nums[i - 1] + 1)
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
1846. 减小和重新排列数组后的最大元素
给你一个正整数数组 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），然后依次让数组的下一个元素满足最多比上一个元素大1，返回数组最后一个值即可。
```
class Solution:
def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
    arr.sort() # O(nlogn)
    if arr[0] != 1:
        arr[0] = 1
    for i in range(1, len(arr)): # O(n)
        if arr[i] > arr[i - 1] + 1:
            arr[i] = arr[i - 1] + 1
    return arr[-1]
```
时间复杂度： $O(nlogn)$ ，其中 n 为 arr 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
1647. 字符频次唯一的最小删除次数
如果字符串 s 中不存在两个不同字符频次相同的情况，就称 s 是优质字符串。给你一个字符串 s，返回使 s 成为优质字符串需要删除的最小字符数。字符串中字符的频次是该字符在字符串中的出现次数。例如，在字符串 ''aab'' 中，'a' 的频次是 2，而 'b' 的频次是 1 。
示例 1：
输入：s = "aab"
输出：0
解释：s 已经是优质字符串。
示例 2：
输入：s = "aaabbbcc"
输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。
示例 3：
输入：s = "ceabaacb"
输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
提示
思路：从最大开始贪心。 要求删除的最小字符数，可以先用一个计数器把数字统计一遍，然后把计数器从大到小排序，数字不能重复出现，因此出现重复的时候当前值比上一个值小 1 即可，遍历完计数器数组（注意当减到 0 的时候，后面的切片和加上 res 即是最后答案）。
```
class Solution:
def minDeletions(self, s: str) -> int:
    from collections import Counter
    nums = []
    nums.extend(Counter(s).values()) # O(n)
    nums.sort(reverse=True) # O(mlogm)
    res = 0
    for i in range(1, len(nums)): # O(m)
        if nums[i] >= nums[i - 1]:
            res += nums[i] - nums[i - 1] + 1
            nums[i] = nums[i - 1] - 1
            if nums[i] == 0:
                return res + sum(nums[i + 1:])
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 是字符串 s 的长度，m 是字符串中不同字符的数量。
空间复杂度： $O(m)$ ，用于存储 Counter 和 nums 列表，忽略排序的栈开销。
重要
整体时间复杂度可以写成： $O(n + mlogm)$ ，由于字符种类数 m 最多为 n，即 m ≤ n，因此整体复杂度可以视为 $O(nlogn)$ 。
2971. 找到最大周长的多边形
给你一个长度为 n 的正整数数组 nums 。多边形指的是一个至少有 3 条边的封闭二维图形。多边形的最长边一定小于所有其他边长度之和。如果你有 k （k >= 3）个正数 a1，a2，a3, ...，ak 满足 a1 <= a2 <= a3 <= ... <= ak 且 a1 + a2 + a3 + ... + ak-1 > ak ，那么一定存在一个 k 条边的多边形，每条边的长度分别为 a1 ，a2 ，a3 ， ...，ak 。一个多边形的周长指的是它所有边之和。请你返回从 nums 中可以构造的多边形的最大周长。如果不能构造出任何多边形，请你返回 -1 。
示例 1：
输入：nums = [5,5,5]
输出：15
解释：nums 中唯一可以构造的多边形为三角形，每条边的长度分别为 5 ，5 和 5 ，周长为 5 + 5 + 5 = 15 。
示例 2：
输入：nums = [1,12,1,2,5,50,3]
输出：12
解释：最大周长多边形为五边形，每条边的长度分别为 1 ，1 ，2 ，3 和 5 ，周长为 1 + 1 + 2 + 3 + 5 = 12 。
我们无法构造一个包含变长为 12 或者 50 的多边形，因为其他边之和没法大于两者中的任何一个。
所以最大周长为 12 。
示例 3：
输入：nums = [5,5,50]
输出：-1
解释：无法构造任何多边形，因为多边形至少要有 3 条边且 50 > 5 + 5 。
提示
思路：从最大开始贪心。 要求周长最大，可以把 nums 从大到小排序，从第一个值开始依次作为最长边判断是否满足多边形条件，注意循环的边界条件。
```
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
    nums.sort(reverse=True) # O(nlogn)
    if len(nums) < 3:
        return -1
    other = sum(nums) - nums[0] # O(n)
    for i in range(len(nums) - 2): # O(n)
        long_num = nums[i]
        if other > long_num:
            return long_num + other
        other -= nums[i + 1]
    return -1
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序的栈开销。
2178. 拆分成最多数目的正偶数之和
给你一个整数 finalSum 。请你将它拆分成若干个互不相同的正偶数之和，且拆分出来的正偶数数目最多。比方说，给你 finalSum = 12 ，那么这些拆分是符合要求的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。请你返回一个整数数组，表示将整数拆分成最多数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个空数组。你可以按任意顺序返回这些整数。
示例 1：
输入：finalSum = 12
输出：[2,4,6]
解释：以下是一些符合要求的拆分：(2 + 10)，(2 + 4 + 6) 和 (4 + 8) 。
(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
[2,6,4] ，[6,2,4] 等等也都是可行的解。
示例 2：
输入：finalSum = 7
输出：[]
解释：没有办法将 finalSum 进行拆分。
所以返回空数组。
示例 3：
输入：finalSum = 28
输出：[6,8,2,12]
解释：以下是一些符合要求的拆分：(2 + 26)，(6 + 8 + 2 + 12) 和 (4 + 24) 。
(6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。
[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。
提示
思路：从最小开始贪心。 要求偶数最多，需要尽可能地选取小的偶数，那么依次选择 2, 4, 6, ... , 直到剩下的数不可再划分。
```
class Solution:
def maximumEvenSplit(self, finalSum: int) -> List[int]:
    if finalSum % 2 == 1:
        return []
    start = 2
    res = []
    while finalSum - start > start:
        finalSum -= start
        res.append(start)
        start += 2
    res.append(finalSum)
    return res
```
时间复杂度： $O(\sqrt{finalSum}))$ 。
空间复杂度： $O(\sqrt{finalSum})$ 。
2567. 修改两个元素的最小分数
给你一个下标从 0 开始的整数数组 nums 。nums 的最小得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。nums的最大得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。nums 的分数是最大得分与最小得分的和。我们的目标是最小化 nums 的分数。你最多可以修改 nums 中 2 个元素的值。请你返回修改 nums 中至多两个元素的值后，可以得到的最小分数。|x| 表示 x 的绝对值
示例 1：
输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。
示例 2：
输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。
提示
思路：要求最小分数，可以先把数组排序，因为可以修改 nums 中至多两个元素的值，所以我们是可以丢掉两个数的（比如nums = [1,4,5,7,8]，那么我们把1和4都变成6，nums = [5,6,6,7,8]，最小得分为0，最大得分为8 - 5 = 3），因此实际上只有三种情况：把最小的2个值丢掉，最小最大值丢掉，最大两个值丢掉，选最小的情况即可。
```
class Solution:
def minimizeSum(self, nums: List[int]) -> int:
    nums.sort() # O(nlogn)
    return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
重要
可以优化成O(n)，因为只用了3个最大值和3个最小值所以中间排序都无所谓，记录3个最大最小值也能做出来。
1509. 三次操作后最大值与最小值的最小差
给你一个数组 nums 。每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。在执行最多三次移动后，返回 nums 中最大值与最小值的最小差值。
示例 1：
输入：nums = [5,3,2,4]
输出：0
解释：我们最多可以走 3 步。
第一步，将 2 变为 3 。 nums 变成 [5,3,3,4] 。
第二步，将 4 改为 3 。 nums 变成 [5,3,3,3] 。
第三步，将 5 改为 3 。 nums 变成 [3,3,3,3] 。
执行 3 次移动后，最小值和最大值之间的差值为 3 - 3 = 0 。
示例 2：
输入：nums = [1,5,0,10,14]
输出：1
解释：我们最多可以走 3 步。
第一步，将 5 改为 0 。 nums变成 [1,0,0,10,14] 。
第二步，将 10 改为 0 。 nums变成 [1,0,0,0,14] 。
第三步，将 14 改为 1 。 nums变成 [1,0,0,0,1] 。
执行 3 步后，最小值和最大值之间的差值为 1 - 0 = 1 。
可以看出，没有办法可以在 3 步内使差值变为0。
示例 3：
输入：nums = [3,100,20]
输出：0
解释：我们最多可以走 3 步。
第一步，将 100 改为 7 。 nums 变成 [3,7,20] 。
第二步，将 20 改为 7 。 nums 变成 [3,7,7] 。
第三步，将 3 改为 7 。 nums 变成 [7,7,7] 。
执行 3 步后，最小值和最大值之间的差值是 7 - 7 = 0。
提示
思路：要求最小分数，可以先把数组排序，因为可以修改 nums 中至多两个元素的值，所以我们是可以丢掉两个数的（比如nums = [1,4,5,7,8]，那么我们把1和4都变成6，nums = [5,6,6,7,8]，最小得分为0，最大得分为8 - 5 = 3），因此实际上只有三种情况：把最小的2个值丢掉，最小最大值丢掉，最大两个值丢掉，选最小的情况即可。
```
class Solution:
def minDifference(self, nums: List[int]) -> int:
    if len(nums) <= 4:
        return 0
    nums.sort() # O(nlogn)
    return min(nums[-4] - nums[0], nums[-3] - nums[1], nums[-2] - nums[2], nums[-1] - nums[3])
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
3397. 执行操作后不同元素的最大数量
给你一个整数数组 nums 和一个整数 k。你可以对数组中的每个元素最多执行一次以下操作：将一个在范围 [-k, k] 内的整数加到该元素上。返回执行这些操作后，nums 中可能拥有的不同元素的最大数量。
示例 1：
输入： nums = [1,2,2,3,3,4], k = 2
输出： 6
解释：
对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。
示例 2：
输入： nums = [4,4,4,4], k = 1
输出： 3
解释：
对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。
提示
思路：要求不同元素数量最大，可以先把 nums 从小到大排序，然后一定会取到最小值（nums[0] - k），然后依次往右增大。具体来说，取出 nums[i] ，左移 k 个单位，如果和上一个元素重复，则 +1 ，即 max(nums[i] - k, pre + 1)，但是 pre + 1 不能超过 nums[i] + k ，所以取一个最小值 min(max(nums[i] - k, pre + 1), nums[i] + k) ，这个就是数组元素 nums[i] 的变化后的值，如果它比上一个元素大（说明是不重复元素），结果 res 加一，遍历 nums 即可。
```
class Solution:
def maxDistinctElements(self, nums: List[int], k: int) -> int:
    res = 0
    nums.sort() # O(nlogn)
    pre = -inf
    for x in nums: # O(n)
        x = min(max(x - k, pre + 1), x + k)
        if x > pre:
            res += 1
            pre = x
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
3457. 吃披萨
给你一个长度为 n 的整数数组 pizzas，其中 pizzas[i] 表示第 i 个披萨的重量。每天你会吃恰好 4 个披萨。由于你的新陈代谢能力惊人，当你吃重量为 W、X、Y 和 Z 的披萨（其中 W <= X <= Y <= Z）时，你只会增加 1 个披萨的重量！体重增加规则如下：在奇数天（按 1 开始计数）你会增加 Z 的重量。在偶数天，你会增加 Y 的重量。请你设计吃掉所有披萨的最优方案，并计算你可以增加的最大总重量。注意：保证 n 是 4 的倍数，并且每个披萨只吃一次。
示例 1：
输入： pizzas = [1,2,3,4,5,6,7,8]
输出： 14
解释：
第 1 天，你吃掉下标为 [1, 2, 4, 7] = [2, 3, 5, 8] 的披萨。你增加的重量为 8。
第 2 天，你吃掉下标为 [0, 3, 5, 6] = [1, 4, 6, 7] 的披萨。你增加的重量为 6。
吃掉所有披萨后，你增加的总重量为 8 + 6 = 14。
示例 2：
输入： pizzas = [2,1,1,1,1,1,1,1]
输出： 3
解释：
第 1 天，你吃掉下标为 [4, 5, 6, 0] = [1, 1, 1, 2] 的披萨。你增加的重量为 2。
第 2 天，你吃掉下标为 [1, 2, 3, 7] = [1, 1, 1, 1] 的披萨。你增加的重量为 1。
吃掉所有披萨后，你增加的总重量为 2 + 1 = 3。
提示
思路：从最大开始贪心。 要求披萨重量之和最大，可以先把 pizzas 从大到小排序，奇数会拿走最大的，偶数会拿走次大的，容易验证最大的数全部给到奇数规则算出来最大，因此分别计算出奇数和偶数的个数 odd_num 和 even_num ，选取前 odd_num 个直接加起来，然后每隔2个数选取一个数加起来，直到 even_num 用完。
```
class Solution:
def maxWeight(self, pizzas: List[int]) -> int:
    pizzas.sort(reverse=True) # O(nlogn)
    odd_num = (len(pizzas) // 4 + 1) // 2
    even_num = len(pizzas) // 4 - odd_num
    res = 0
    res += sum(pizzas[: odd_num])

    odd_num += 1
    while even_num > 0:
        res += pizzas[odd_num]
        odd_num += 2
        even_num -= 1
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。

10.1.2 单序列配对

同上，从最小/最大的元素开始贪心。

2144. 打折购买糖果的最小开销
一家商店正在打折销售糖果。每购买两个糖果，商店会免费送一个糖果。免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的较小值。比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得所有糖果的最小总开销。
示例 1：
输入：cost = [1,2,3]
输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的唯一方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
示例 2：
输入：cost = [6,5,7,9,2,2]
输出：23
解释：最小总开销购买糖果方案为：
- 购买价格为 9 和 7 的糖果
- 免费获得价格为 6 的糖果
- 购买价格为 5 和 2 的糖果
- 免费获得价格为 2 的最后一个糖果
  因此，最小总开销为 9 + 7 + 5 + 2 = 23 。
示例 3：
输入：cost = [5,5]
输出：10
解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。
所以总最小开销为 5 + 5 = 10 。
提示
思路：从最大开始贪心，相邻三个元素为序列。 要求花费最小，我们需要赠送的糖果价值尽可能地大，可以先从大到小排序，然后每三个为一组012，购买第一个和第二个，赠送第三个（即余数为2的）。
```
class Solution:
def minimumCost(self, cost: List[int]) -> int:
    cost.sort(reverse=True) # O(nlogn)
    res = 0
    for i in range(len(cost)):
        if i % 3 != 2:
            res += cost[i]
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 cost 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
561. 数组拆分
给定长度为 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
提示
思路：从最小开始贪心，相邻两个元素为序列。 要求最小值的和最大，很明显，最小值的两个数差距越小最后的和越大，因此可以排序后两个一组取最小值然后求和即可。
```
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
    nums.sort() # O(nlogn)
    res = 0
    for i in range(0, len(nums), 2):
        res += min(nums[i], nums[i + 1])
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
1877. 数组中最大数对和的最小值
一个数对 (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 。
提示
思路：从最小开始贪心，首尾两个元素为序列。 要求最大数对和最小，和上一题不同，这题我们要保证数对和之间的差距不大，这样求出的数对和会比较小，因此使用两个指针分别指向起始和末尾，都往中间走，这样就可以保证求出的数对和比较均匀。
```
class Solution:
def minPairSum(self, nums: List[int]) -> int:
    nums.sort() # O(nlogn)
    res = -inf
    left = 0
    right = len(nums) - 1
    while left < right:
        res = max(res, nums[left] + nums[right])
        left += 1
        right -= 1
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
881. 救生艇
给定数组 people 。people[i]表示第 i 个人的体重，船的数量不限，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回承载所有人所需的最小船数
示例 1：
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
提示
思路：从最大开始贪心，首尾两个元素为序列。 要求船数最少，可以先从大到小排序，然后首尾组成一个序列，如果序列的和没有超过 limit 就合法，否则大的数只能单独使用一条船。
```
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
    people.sort(reverse=True) # O(nlogn)
    left = 0
    right = len(people) - 1
    res = 0
    while left < right: # O(n)
        if people[left] == limit:
            res += 1
            left += 1
            continue
        if people[left] + people[right] <= limit:
            right -= 1
        res += 1
        left += 1
    return res + 1 if left == right else res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 people 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
2592. 最大化数组的伟大值
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。定义 nums 的伟大值为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。请你返回重新排列 nums 后的最大伟大值。
示例 1：
输入：nums = [1,3,5,2,1,3,1]
输出：4
解释：一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。
在下标为 0, 1, 3 和 4 处，都有 perm[i] > nums[i] 。因此我们返回 4 。
示例 2：
输入：nums = [1,2,3,4]
输出：3
解释：最优排列为 [2,3,4,1] 。
在下标为 0, 1 和 2 处，都有 perm[i] > nums[i] 。因此我们返回 3 。
提示
思路：从最大开始贪心，两个元素为序列。 要求伟大值最大，这题类似田忌赛马，需要让次小值尽可能地匹配最小值。
```
class Solution:
def maximizeGreatness(self, nums: List[int]) -> int:
    nums.sort() # O(nlogn)
    left = 0
    for num in nums: # O(n)
        if num > nums[left]:
            left += 1
    return left
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
2576. 求出最多标记下标
给你一个下标从 0 开始的整数数组 nums 。一开始，所有下标都没有被标记。你可以执行以下操作任意次：选择两个互不相同且未标记的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。
示例 1：
输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。
示例 2：
输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。
示例 3：
输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。
提示
思路：从最大开始贪心，两个元素为序列。 要求配队的数尽可能地多，可以把 nums 分成两半，判断前半部分有多少能满足 2 * nums[i] <= nums[j] 。
```
class Solution:
def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
    nums.sort() # O(nlogn)
    left = 0
    for num in nums[(len(nums) + 1) // 2:]:
        if nums[left] * 2 <= num:
            left += 1
    return left * 2
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。

10.1.3 双序列配队

同上，从最小/最大的元素开始贪心。

2037. 使每位学生都有座位的最少移动次数
一个房间里有 n 个空闲座位和 n 名站着的学生，房间用一个数轴表示。给你一个长度为 n 的数组 seats ，其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ，其中 students[j] 是第 j 位学生的位置。你可以执行以下操作任意次：增加或者减少第 i 位学生的位置，每次变化量为 1 （也就是将第 i 位学生从位置 x 移动到 x + 1 或者 x - 1）请你返回使所有学生都有座位坐的最少移动次数，并确保没有两位学生的座位相同。请注意，初始时有可能有多个座位或者多位学生在同一位置。
示例 1：
输入：seats = [3,1,5], students = [2,7,4]
输出：4
解释：学生移动方式如下：
- 第一位学生从位置 2 移动到位置 1 ，移动 1 次。
- 第二位学生从位置 7 移动到位置 5 ，移动 2 次。
- 第三位学生从位置 4 移动到位置 3 ，移动 1 次。
  总共 1 + 2 + 1 = 4 次移动。
示例 2：
输入：seats = [4,1,5,9], students = [1,3,2,6]
输出：7
解释：学生移动方式如下：
- 第一位学生不移动。
- 第二位学生从位置 3 移动到位置 4 ，移动 1 次。
- 第三位学生从位置 2 移动到位置 5 ，移动 3 次。
- 第四位学生从位置 6 移动到位置 9 ，移动 3 次。
  总共 0 + 1 + 3 + 3 = 7 次移动。
示例 3：
输入：seats = [2,2,6,6], students = [1,3,2,6]
输出：4
解释：学生移动方式如下：
- 第一位学生从位置 1 移动到位置 2 ，移动 1 次。
- 第二位学生从位置 3 移动到位置 6 ，移动 3 次。
- 第三位学生不移动。
- 第四位学生不移动。
  总共 1 + 3 + 0 + 0 = 4 次移动。
提示
思路：双序列配队。 要求最少移动次数，先对两个数组排序，然后把对应位置的元素绝对值之差求和即可。
```
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
    seats.sort() # O(nlogn)
    students.sort() # O(nlogn)
    res = 0
    for i, j in zip(seats, students): # O(n)
        res += abs(i - j)
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 seats 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 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。
提示
思路：双序列配队。 要求尽可能多地满足孩子，先对两个数组排序，然后遍历饼干，依次把小饼干分配给胃口小的孩子，看能分出去多少饼干。
```
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
    g.sort() # O(mlogm)
    s.sort() # O(nlogn)
    i = 0
    for x in s: # O(n)
        if x >= g[i]:
            i += 1
            if i == len(g):
                return i
    return i
```
时间复杂度： $O(nlogn)$ ，其中 n 为 s 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
2410. 运动员和训练师的最大匹配数
给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的能力值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的训练能力值。如果第 i 名运动员的能力值小于等于第 j 名训练师的能力值，那么第 i 名运动员可以匹配第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。请你返回满足上述要求 players 和 trainers 的最大匹配数。
示例 1：
输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
  可以证明 2 是可以形成的最大匹配数。
示例 2：
输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。
提示
思路：双序列配队。 和上一题分饼干思路一模一样。
```
class Solution:
def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
    players.sort() # O(mlogm)
    trainers.sort() # O(nlogn)
    i = 0
    for x in trainers: # O(n)
        if x >= players[i]:
            i += 1
            if i == len(players):
                return i
    return i
```
时间复杂度： $O(nlogn)$ ，其中 n 为 trainers 的长度。
空间复杂度： $O(1)$ ，忽略排序时栈的开销。
1433. 检查一个字符串是否可以打破另一个字符串
给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。
示例 1：
输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
示例 2：
输入：s1 = "abe", s2 = "acd"
输出：false
解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。
示例 3：
输入：s1 = "leetcodee", s2 = "interview"
输出：true
提示
思路：双序列配队。 可以先把字符串转化成列表，然后使用 sort 函数按照字典序排序，一一对比是否全小或者全大即可。
```
class Solution:
def checkIfCanBreak(self, s1: str, s2: str) -> bool:
    s1_list = list(s1)
    s2_list = list(s2)
    s1_list.sort() # O(nlogn)
    s2_list.sort() # O(nlogn)
    return all(i >= j for i, j in zip(s1_list, s2_list)) or all(i <= j for i, j in zip(s1_list, s2_list)) # O(n)
```
时间复杂度： $O(nlogn)$ ，其中 n 为 s1 的长度。
空间复杂度： $O(n)$ ，忽略排序时栈的开销。
870. 优势洗牌
给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
示例 1：
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]
示例 2：
输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]
提示
思路：双序列配队。 田忌赛马，但是需要保留序列。先把 nums1 排序，从最小的马开始和 nums2 最小的马比较（nums2 需要保留顺序，因此不能排序，可以使用一个列表 idx 存储 nums2 的从小到大的索引），如果 nums1 的下等马比 nums2 的下等马厉害，就在结果 res 的 idx 下等马位置保存，如果 nums1 的下等马比 nums2 的下等马差，就在结果 res 的 idx 上等马位置保存（用驽马换良驹）。
```
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
    n = len(nums1)
    nums1.sort() # O(nlogn)
    idx = sorted(range(n), key=lambda i:nums2[i]) # O(nlogn)
    left = 0
    right = n - 1
    res = [0] * n
    for num1 in nums1: # O(n)
        if num1 <= nums2[idx[left]]: # 用驽马换良驹
            res[idx[right]] = num1
            right -= 1
        else:
            res[idx[left]] = num1 # 用下等马打过下等马
            left += 1
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums1 的长度。
空间复杂度： $O(n)$ ，忽略排序时栈的开销。
826. 安排工作以达到最大收益
你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。每个工人最多只能安排一个工作，但是一个工作可以完成多次。举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。返回在把工人分配到工作岗位后，我们所能获得的最大利润。
示例 1：
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。
示例 2：
输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0
提示
思路：双序列配队。 这题的坑是困难任务不一定报酬高，因此我们需要绑定 difficulty 和 profit 排序，按照任务困难从小到大遍历，记录工人能完成的任务中的利润最大值。
```
class Solution:
def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
    jobs = sorted(zip(difficulty, profit)) # O(mlogm)
    worker.sort() # O(nlogn)
    res = 0
    max_profit = 0
    j = 0
    for w in worker: # O(n)
        while j < len(difficulty) and w >= jobs[j][0]:
            max_profit = max(max_profit, jobs[j][1])
            j += 1
        res += max_profit
    return res
```
时间复杂度： $O(mlogm + nlogn)$ ，其中 m 为 difficulty 的长度，n 为 worker 的长度。
空间复杂度： $O(n)$ ，忽略排序时栈的开销。

10.1.4 从最左/最右开始贪心

对于无法排序的题目，尝试从左到右/从右到左贪心。思考第一个数/最后一个数的贪心策略，把 n 个数的原问题转换成 n−1 个数（或更少）的子问题。

读者可以对比下面的题目和动态规划题单中的线性 DP、状态机 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。

3402. 使每一列严格递增的最少操作次数
给你一个由非负整数组成的 m x n 矩阵 grid。在一次操作中，你可以将任意元素 grid[i][j] 的值增加 1。返回使 grid 的所有列严格递增所需的最少操作次数。
示例 1：
输入: grid = [[3,2],[1,3],[3,4],[0,1]]
输出: 15
解释:
为了让第 0 列严格递增，可以对 grid[1][0] 执行 3 次操作，对 grid[2][0] 执行 2 次操作，对 grid[3][0] 执行 6 次操作。
为了让第 1 列严格递增，可以对 grid[3][1] 执行 4 次操作。
示例 2：
输入: grid = [[3,2,1],[2,1,0],[1,2,3]]
输出: 12
解释:
为了让第 0 列严格递增，可以对 grid[1][0] 执行 2 次操作，对 grid[2][0] 执行 4 次操作。
为了让第 1 列严格递增，可以对 grid[1][1] 执行 2 次操作，对 grid[2][1] 执行 2 次操作。
为了让第 2 列严格递增，可以对 grid[1][2] 执行 2 次操作。
提示
思路：外层遍历每一列，内层去模拟，如果当前值小于等于上一行的值，那么需要操作上一个值 + 1 减去当前值的操作次数，然后更新当前值。
```
class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    res = 0
    for j in range(n): # O(n)
        for i in range(1, m): # O(m)
            if grid[i][j] <= grid[i - 1][j]:
                res += grid[i - 1][j] + 1 - grid[i][j]
                grid[i][j] = grid[i - 1][j] + 1
    return res
```
时间复杂度： $O(mn)$ ，其中 m 为 grid 的行数，n 为 grid 的列数。
空间复杂度： $O(1)$ 。
3191. 使二进制数组全部等于 1 的最少操作次数 I
给你一个二进制数组 nums 。你可以对数组执行以下操作任意次（也可以 0 次）：选择数组中任意连续 3 个元素，并将它们全部反转。反转一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。请你返回将 nums 中所有元素变为 1 的最少操作次数。如果无法全部变成 1 ，返回 -1 。
示例 1：
输入：nums = [0,1,1,1,0,0]
输出：3
解释：
我们可以执行以下操作：
选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。
选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。
选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。
示例 2：
输入：nums = [0,1,1,1]
输出：-1
解释：
无法将所有元素都变为 1 。
提示
思路：感觉纯纯模拟，贪心不了一点。从左到右遍历，如果当前值是0，那么改变连续的三个值，用 1 减去当前值就可以实现 0 变 1 ，1 变 0 ，最后判断最后两个元素是否为 0 ，如果为 0 说明变不了。
```
class Solution:
def minOperations(self, nums: List[int]) -> int:
    res = 0
    for i in range(len(nums) - 2):
        if nums[i] == 0:
            res += 1
            nums[i] = 1
            nums[i + 1] = 1 - nums[i + 1]
            nums[i + 2] = 1 - nums[i + 2]
    return -1 if 0 in nums[-2:] else res
```
时间复杂度： $O(mn)$ ，其中 m 为 grid 的行数，n 为 grid 的列数。
空间复杂度： $O(1)$ 。
1827. 最少操作使数组递增
给你一个整数数组 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
提示
思路：这题和第一题一毛一样。
```
class Solution:
def minOperations(self, nums: List[int]) -> int:
    res = 0
    for i in range(1, len(nums)): # O(n)
        if nums[i] <= nums[i - 1]:
            res += nums[i - 1] + 1 - nums[i]
            nums[i] = nums[i - 1] + 1
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。
2027. 转换字符串的最少操作次数
给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。一次操作定义为从 s 中选出三个连续字符并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持不变。返回将 s 中所有字符均转换为 'O' 需要执行的最少操作次数。
示例 1：
输入：s = "XXX"
输出：1
解释：XXX -> OOO
一次操作，选中全部 3 个字符，并将它们转换为 'O' 。
示例 2：
输入：s = "XXOX"
输出：2
解释：XXOX -> OOOX -> OOOO
第一次操作，选择前 3 个字符，并将这些字符转换为 'O' 。
然后，选中后 3 个字符，并执行转换。最终得到的字符串全由字符 'O' 组成。
示例 3：
输入：s = "OOOO"
输出：0
解释：s 中不存在需要转换的 'X' 。
提示
思路：纯纯模拟。从左往右遍历，如果是 X ，则后三位变为 0 ，并且 i 后移三位，不是 X 则遍历下一位。
```
class Solution:
def minimumMoves(self, s: str) -> int:
    s_list = list(s)
    res = 0
    i = 0
    while i < len(s) - 2: # O(n)
        if s_list[i] == 'X':
            res += 1
            s_list[i] = '0'
            s_list[i + 1] = '0'
            s_list[i + 2] = '0'
            i += 3
        else:
            i += 1
    return res + 1 if 'X' in s_list[-2:] else res
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
605. 种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 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
提示
思路：先统计出还能种多少，然后和 n 比较即可。只有访问到 0 0 0 才能在中间种花，然后变成 0 1 0 ，为了代码简便，我们可以在数组前后各加一个 0 。
```
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
    flowerbed.insert(0, 0) # O(n)
    flowerbed.append(0) # O(1)
    free = 0
    i = 1
    while i < len(flowerbed) - 1: # O(n)
        if flowerbed[i] == 0 and flowerbed[i - 1] == 0 and flowerbed[i + 1] == 0:
            flowerbed[i] = 1
            free += 1
            i += 1
        i += 1
    return free >= n
```
时间复杂度： $O(n)$ ，其中 n 为 flowerbed 的长度。
空间复杂度： $O(1)$ 。
3111. 覆盖所有点的最少矩形数目
给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形覆盖所有点。每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都必须满足 x2 - x1 <= w 。如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。请你在确保每个点都至少被一个矩形覆盖的前提下，最少需要多少个矩形。注意：一个点可以被多个矩形覆盖。
示例 1：
输入：points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出：2
解释：
上图展示了一种可行的矩形放置方案：（图片请看leetcode页面）
一个矩形的左下角在 (1, 0) ，右上角在 (2, 8) 。
一个矩形的左下角在 (3, 0) ，右上角在 (4, 8) 。
示例 2：
输入：points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出：3
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (0, 0) ，右上角在 (2, 2) 。
一个矩形的左下角在 (3, 0) ，右上角在 (5, 5) 。
一个矩形的左下角在 (6, 0) ，右上角在 (6, 6) 。
示例 3：
输入：points = [[2,3],[1,2]], w = 0
输出：2
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (1, 0) ，右上角在 (1, 2) 。
一个矩形的左下角在 (2, 0) ，右上角在 (2, 3) 。
提示
思路：可以不用管纵坐标，只关注横坐标，如果当前值比矩形右边界大，则新建一个矩形，右边界更新为当前值 + w 。
```
class Solution:
def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
    points.sort(key=lambda p: p[0]) # O(nlogn)
    points
    x1 = -1
    res = 0
    for x, _ in points:
        if x > x1:
            res += 1
            x1 = x + w
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 points 的长度。
空间复杂度： $O(1)$ 。忽略排序的栈开销。
2957. 消除相邻近似相等字符
给你一个下标从 0 开始的字符串 word 。一次操作中，你可以选择 word 中任意一个下标 i ，将 word[i] 修改成任意一个小写英文字母。请你返回消除 word 中所有相邻近似相等字符的最少操作次数。两个字符 a 和 b 如果满足 a == b 或者 a 和 b 在字母表中是相邻的，那么我们称它们是近似相等字符。
示例 1：
输入：word = "aaaaa"
输出：2
解释：我们将 word 变为 "acaca" ，该字符串没有相邻近似相等字符。
消除 word 中所有相邻近似相等字符最少需要 2 次操作。
示例 2：
输入：word = "abddez"
输出：2
解释：我们将 word 变为 "ybdoez" ，该字符串没有相邻近似相等字符。
消除 word 中所有相邻近似相等字符最少需要 2 次操作。
示例 3：
输入：word = "zyxyxyz"
输出：3
解释：我们将 word 变为 "zaxaxaz" ，该字符串没有相邻近似相等字符。
消除 word 中所有相邻近似相等字符最少需要 3 次操作
提示
思路：从左到右遍历，如果当前值和上一个相近，那么当前值会被假装修改，即指针后移两位，否则后移一位。
```
class Solution:
def removeAlmostEqualCharacters(self, word: str) -> int
    i = 1
    res = 0
    while i < len(word): # O(n)
        if abs(ord(word[i]) - ord(word[i - 1])) <= 1:
            res += 1
            i += 2
        else:
            i += 1
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 word 的长度。
空间复杂度： $O(1)$ 。
重要
ord() 是一个内置函数，用于将单个字符转换为其对应的Unicode 编码整数值。
```
print(ord('A'))    # 输出 65
print(ord('a'))    # 输出 97
print(ord('中'))   # 输出 20013
```
3192. 使二进制数组全部等于 1 的最少操作次数 II
给你一个二进制数组 nums 。你可以对数组执行以下操作任意次（也可以 0 次）：选择数组中任意一个下标 i ，并将从下标 i 开始一直到数组末尾所有元素反转。反转一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。请你返回将 nums 中所有元素变为 1 的最少操作次数。
示例 1：
输入：nums = [0,1,1,0,1]
输出：4
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。
选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。
选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。
选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。
示例 2：
输入：nums = [1,0,0,0]
输出：1
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [1,1,1,1] 。
提示
思路：这题很难模拟，因此考虑将大问题化简成n - 1的子问题：如果当前元素是1，不需要操作，问题变成剩下 n−1 个数的子问题；如果是0，需要操作，问题变成剩下 n−1 个数（在操作次数是 1 的情况下）的子问题。对后续元素来说，由于反转偶数次等于没反转，所以只需考虑操作次数的奇偶性。
```
class Solution:
def minOperations(self, nums: List[int]) -> int:
    res = 0
    for x in nums: # O(n)
        if x == res % 2:
            res += 1
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。
2789. 合并后数组中的最大元素
给你一个下标从 0 开始、由正整数组成的数组 nums 。你可以在数组上执行下述操作任意次：选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。返回你可以从最终数组中获得的最大元素的值。
示例 1：
输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
  最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
示例 2：
输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
  最终数组中只有一个元素，即 11 。
提示
思路：从右往左遍历，类似“大鱼吃小鱼”，如果右边元素大于等于左边元素，那么左边元素可以加上右边元素。
```
class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
    for i in range(len(nums) - 2, -1, -1): # O(n)
        if nums[i] <= nums[i + 1]:
            nums[i] += nums[i + 1]
    return nums[0]
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。
1529. 最少的后缀翻转次数
给你一个长度为 n 、下标从 0 开始的二进制字符串 target 。你自己有另一个长度为 n 的二进制字符串 s ，最初每一位上都是 0 。你想要让 s 和 target 相等。在一步操作，你可以选择下标 i（0 <= i < n）并翻转在闭区间 [i, n - 1] 内的所有位。翻转意味着 '0' 变为 '1' ，而 '1' 变为 '0' 。返回使 s 与 target 相等需要的最少翻转次数。
示例 1：
输入：target = "10111"
输出：3
解释：最初，s = "00000" 。
选择下标 i = 2: "00000" -> "00111"
选择下标 i = 0: "00111" -> "11000"
选择下标 i = 1: "11000" -> "10111"
要达成目标，需要至少 3 次翻转。
示例 2：
输入：target = "101"
输出：3
解释：最初，s = "000" 。
选择下标 i = 0: "000" -> "111"
选择下标 i = 1: "111" -> "100"
选择下标 i = 2: "100" -> "101"
要达成目标，需要至少 3 次翻转。
示例 3：
输入：target = "00000"
输出：0
解释：由于 s 已经等于目标，所以不需要任何操作
提示
思路：从左往右遍历，如果当前值与翻转次数奇偶性不同则需要翻转。
```
class Solution:
def minFlips(self, target: str) -> int:
    res = 0
    for c in target: # O(n)
        if int(c) % 2 != res % 2:
            res += 1
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 target 的长度。
空间复杂度： $O(1)$ 。
1144. 递减元素使数组呈锯齿状
给你一个整数数组 nums，每次操作会从中选择一个元素并将该元素的值减少 1。如果符合下列情况之一，则数组 A 就是锯齿数组：每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...返回将数组 nums 转换为锯齿数组所需的最小操作次数。
示例 1：
输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。
示例 2：
输入：nums = [9,6,1,6,2]
输出：4
提示
思路：阿囧的两次遍历分别遍历奇数和偶数的懒人抽象解法，一次遍历可以参考灵神的题解。
```
class Solution:
def movesToMakeZigzag(self, nums: List[int]) -> int:
    nums.insert(0, float('inf'))
    nums.append(float('inf'))
    bak_nums = nums.copy()
    res1 = 0
    res2 = 0
    for i in range(1, len(nums) - 1, 2): # O(n)
        temp_min = min(nums[i - 1], nums[i + 1])
        if nums[i] >= temp_min:
            res1 += nums[i] - temp_min + 1
            nums[i] = temp_min - 1

    for i in range(2, len(nums) - 1, 2): # O(n)
        temp_min = min(bak_nums[i - 1], bak_nums[i + 1])
        if bak_nums[i] >= temp_min:
            res2 += bak_nums[i] - temp_min + 1
            bak_nums[i] = temp_min - 1

    return min(res1, res2)
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(n)$ 。
3228. 将 1 移动到末尾的最大操作次数
给你一个二进制字符串 s。你可以对这个字符串执行任意次下述操作：选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。将字符 s[i] 向右移直到它到达字符串的末端或另一个 '1'。例如，对于 s = '010010'，如果我们选择 i = 1，结果字符串将会是 s = '000110'。返回你能执行的最大操作次数。
示例 1：
输入： s = "1001101"
输出： 4
解释：
可以执行以下操作：
选择下标 i = 0。结果字符串为 s = "0011101"。
选择下标 i = 4。结果字符串为 s = "0011011"。
选择下标 i = 3。结果字符串为 s = "0010111"。
选择下标 i = 2。结果字符串为 s = "0001111"。
示例 2：
输入： s = "00111"
输出： 0
提示
思路：用 one_num 来记录 1 出现的次数，如果当前元素是 1 ，并且下一个元素是 0 ，那么触发移动，可移动次数即 one_num 的值。
```
class Solution:
def maxOperations(self, s: str) -> int:
    one_num = 0
    res = 0
    for i in range(len(s) - 1): # O(n)
        if s[i] == '1':
            one_num += 1
            if s[i + 1] == '0':
                res += one_num
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(1)$ 。
2086. 喂食仓鼠的最小食物桶数
给你一个下标从 0 开始的字符串 hamsters ，其中 hamsters[i] 要么是：'H' 表示有一个仓鼠在下标 i ，或者 '.' 表示下标 i 是空的。你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶，就可以喂食它。更正式地说，如果你在位置 i - 1 或者 i + 1 放置一个食物桶，就可以喂养位置为 i 处的仓鼠。在空的位置放置食物桶以喂养所有仓鼠的前提下，请你返回需要的最少食物桶数。如果无解请返回 -1 。
示例 1：
输入：hamsters = "H..H"
输出：2
解释：
我们可以在下标为 1 和 2 处放食物桶。
可以发现如果我们只放置 1 个食物桶，其中一只仓鼠将得不到喂养。
示例 2：
输入：street = ".H.H."
输出：1
解释：
我们可以在下标为 2 处放置一个食物桶。
示例 3：
输入：street = ".HHH."
输出：-1
解释：
如果我们如图那样在每个空位放置食物桶，下标 2 处的仓鼠将吃不到食物。
提示
思路：先去除无解的情况（HH在开头、HH在结尾、含有HHH、整体是一个H），剩下的一定有解，那么正常来说一只鼠鼠就要有一个甜甜圈，但这里如果有 "H.H" ，是可以节省一个甜甜圈的，因此用 replace 替换 "H.H" 为 "H" ，再统计鼠鼠的个数即可。
```
class Solution:
def minimumBuckets(self, hamsters: str) -> int:
    if hamsters[:2] == "HH" or hamsters[-2:] == "HH" or "HHH" in hamsters or hamsters == "H":
        return -1
    hamsters = hamsters.replace("H.H", "H")
    return hamsters.count("H")
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(1)$ 。

10.1.5 划分型贪心

把数组/字符串划分成满足要求的若干段，最小化/最大化划分的段数。

思考方法同上，尝试从左到右/从右到左贪心。

读者可以对比下面的题目和动态规划题单中的划分型 DP 的区别，思考什么情况下只能 DP 不能贪心，从而加深对「局部最优」和「全局最优」的理解。

1221. 分割平衡字符串
平衡字符串中，'L' 和 'R' 字符的数量是相同的。给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：每个子字符串都是平衡字符串。返回可以通过分割得到的平衡字符串的最大数量。
示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
示例 2：
输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。
示例 3：
输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。
提示
思路：遍历字符串，用两个变量维护 L 和 R 的数量，如果一致了则结果加一且归零。
```
class Solution:
def balancedStringSplit(self, s: str) -> int:
    l_num = 0
    r_num = 0
    res = 0
    for c in s: # O(n)
        if c == 'R':
            r_num += 1
        else:
            l_num += 1
        if l_num == r_num:
            res += 1
            l_num = 0
            r_num = 0
    return res
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(1)$ 。
2405. 子字符串的最优划分
给你一个字符串 s ，请你将该字符串划分成一个或多个子字符串，并满足每个子字符串中的字符都是唯一的。也就是说，在单个子字符串中，字母的出现次数都不超过一次。满足题目要求的情况下，返回最少需要划分多少个子字符串。注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。
示例 1：
输入：s = "abacaba"
输出：4
解释：
两种可行的划分方法分别是 ("a","ba","cab","a") 和 ("ab","a","ca","ba") 。
可以证明最少需要划分 4 个子字符串。
示例 2：
输入：s = "ssssss"
输出：6
解释：
只存在一种可行的划分方法 ("s","s","s","s","s","s") 。
提示
思路：遍历字符串，用计数器来维护当前不重复的元素种类，如果遇到重复的元素，结果 + 1 ，清空计数器，最后如果计数器里还有元素，则单独成为一个子字符串。
```
class Solution:
def partitionString(self, s: str) -> int:
    from collections import defaultdict
    cnt = defaultdict(int)
    res = 0
    for c in s: # O(n)
        if cnt[c] != 0:
            res += 1
            cnt.clear()
        cnt[c] += 1
    return res + 1 if cnt else res
```
时间复杂度： $O(n)$ ，其中 n 为 s 的长度。
空间复杂度： $O(n)$ 。
2294. 划分数组使最大差为 K
给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个子序列，使 nums 中的每个元素都恰好出现在一个子序列中。在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的最少子序列数目。子序列本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。
示例 1：
输入：nums = [3,6,1,2,5], k = 2
输出：2
解释：
可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。
示例 2：
输入：nums = [1,2,3], k = 1
输出：2
解释：
可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。
示例 3：
输入：nums = [2,2,4,5], k = 0
输出：3
解释：
可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。
提示
思路：先排序，根据第一个元素加上k可以确定右侧边界，超过右侧边界需要新开辟一个序列。
```
class Solution:
def partitionArray(self, nums: List[int], k: int) -> int:
    nums.sort() # O(nlogn)
    res = 1
    max_num = nums[0] + k
    for num in nums: # O(n)
        if num <= max_num:
            continue
        res += 1
        max_num = num + k
    return res
```
时间复杂度： $O(nlogn)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。