力扣刷题笔记 #07 贪心算法

本文最后更新于：2023年9月19日晚上

本文包含「贪心算法」类型题中的：扫描贪心、置换环贪心、单调队列贪心、排序贪心等。持续更新中。

题目描述：
方法1：
方法2：
方法3：
坑点：

满足「重叠子问题 + 贪心选择性」的问题。通常涉及一定的思维量，以及巧妙的构造。

扫描贪心

31. 下一个排列 (M)

题目描述：给定整数数组的一个排列，生成字典序的下一个排列。数字可能有重复，要求原地修改。

方法1：贪心 + 两次反向扫描，第一次扫描找到首个「下降数」，将该数与右边的数交换就能将排列变大；第二次找到「比下降数大的第一个数」，将两数交换，右边的数字逆序即可。时间复杂度 \(O(n)\)。

由于按字典序的下一个排列会比当前要大，但是要让变大的幅度尽可能小。观察排列的变化规律，发现从后往前一直会有递增关系，直到遇到第一个下降数（且不能是相等的）。可以证明，如果只改变「下降数」右边的序列，结果不可能更大。
因此必须取代下降数，而每次取代下降数的则是右边一个比之稍大的数（同样不能是相等的，否则交换没有意义）。将两数交换后，整个排列必然会增大，为了能让变大的幅度尽可能小，右边的序列就需要逆序成升序序列。
但是如果没有找到下降数，则说明整个序列已经是降序，此时无需直接逆转即可。

方法2：C++ 函数 netx_permutation(a,a+n) 实现了方法 1 的功能。

55. 跳跃游戏 (M)

题目描述：给定一个非负整数数组，数组中的每个元素代表在该位置可以跳跃的最大长度，判断能否从第一个元素跳到最后一个元素。

方法1：贪心，只需考虑向前跳（向后跳意味着循环）。为了不漏掉每个可能的转移，需要扫描跳跃范围内的所有元素，贪心维护「能跳到的最右范围」，每次遇到更大的就更新。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法2：贪心，维护「剩余还能跳的步数」，逐步递减，每次遇到更大的就更新。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

670. 最大交换 (M)

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

方法1：暴力，遍历所有可能的交换方式，复杂度 \(O(k^2)\)，\(k\) 为位数。

方法2：贪心，每一个数字只能和其左侧相对小的数字交换，且不能跨越比它更大的数字，因为比它更大的数字往左交换的收益更高。因此从右往左扫描，记录当前最大的数及其可以交换的最远距离，复杂度 \(O(k)\)。

扩展：这类问题需要把整数当作序列来操作，可以结合 to_string() 和 stoi() 函数。

11. 盛最多水的容器 (M)

题目描述：给定一个长度为 n 的数组表示 n 条垂线的高，找出其中两条线，使它们构成的容器能装最多的水。

方法1：暴力，两层循环，先选中左边界，再遍历右边界，时间复杂度 \(O(n^2)\)。

方法2：贪心 + 对撞双指针，双指针从两端开始遍历，选定两个边界中的短板，向中间收窄一格。时间复杂度 \(O(n)\)。

贪心选择性证明：在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度变短。
若向内移动短板 ，水槽的短板可能变大，因此下个水槽的面积可能增大。
若向内移动长板 ，水槽的短板不变或变小，因此下个水槽的面积一定变小。
因此每轮向内移动短板，都会消去「不可能成为最大值的状态」。

581. 最短无序连续子数组 (M)

题目描述：给定一个整数数组，从中找出一个最短连续子数组，如果对这个子数组排序，那么整个数组都会变为升序。

方法1：索引排序，对整个数组进行索引排序，再从两边扫描第一个 idx[i]!=i 的位置，时间复杂度 \(O(n\log n)\)。为了防止重复数导致不稳定，应采用 stable_sort()。

方法2：贪心，从左往右扫描并维护最大值，如果新遇到一个元素小于最大值，则该元素必定无序，扩展右边界；同理，从右往左维护最小值，扩展左边界。时间复杂度 \(O(n)\)。

贪心选择性证明：整个数组必定会呈现「有序 + 无序 + 有序」的排列，而无序段的所有元素都要大于左段的最大值、小于右段的最小值。
因此，从左往右扫描时如果遇到一个元素小于最大值，则其不可能处于右段（因为右段必须更大、且升序），不可能处于左段（因为左段必须升序），则其必定在无序段中。

621. 任务调度器 (M)

题目描述：给定一个字符数组表示任务列表，每个大写母代表一种不同种类的任务，任务可以按任何顺序执行，每次执行需要一个单位时间。但两个相同种类的任务之间需要有 n 的冷却时间。计算完成所有任务所需的最短时间。

方法1：贪心 + 构造，先用桶记录下每种任务出现的次数，再降序排列。最后按照如下方式构造解：

假设出现最多的任务是 \(A\)，则至少要形成 \(A** +A**+A\) 的序列，为了尽量利用空间，我们要将剩余任务插入到 \(*\) 位置。此时最短长度为 \((hash[A]-1)\times (n+1)+1\)。
注意到如果其他任务的次数和 \(A\) 一样多，则会形成 \(AB*+AB*+AB\) 的序列，即末尾扩充。而如果其他任务比 \(A\) 少，直接插入到空位即可，必然会满足冷却时间。
当所有 \(*\) 位置都插满后，剩余的任务可以直接补到每一组子序列之后，例如 \(ABCD+ABCD+AB\)，此时所有的 \(D\) 之间间隔都大于 n，且无需新的 \(*\) 占位。此时答案就是 tasks 的总数。

135. 分发糖果 (H)

题目描述：给定大小为 n 的数组表示 n 个孩子的评分，要求每个孩子至少分到一个糖果，且相邻两个孩子评分更高的孩子会获得更多的糖果，求最少需要的糖果数目。

方法1：记忆化搜索，DFS 终止条件是相邻点评分大于等于当前点，否则就先 DFS 求出邻居的结果。用 vis 数组记录访问过的点，时空复杂度均为 \(O(n)\)。

方法2：贪心 + 两遍扫描，第一遍从左到右扫描，初始化一个全 1 的数组 left，再对所有 r[i]<r[i+1] 的情况维护，其他情况不变；同理从右到左维护一个 right，最后取二者中最大值即为答案。时空复杂度均为 \(O(n)\)。

贪心选择性证明：任取序列中相邻的两点 A 和 B，如果 A < B，则从左到右扫描后，B 的糖果一定比 A 多；且从右到左扫描后，A 的糖果不会变得更多，因此满足两个规则。同理 A > B 也成立，而当 A = B 时，二者的值不相互影响。综上所述，取最大值后两个规则都能成立。

方法3：贪心 + 一遍扫描，同时考虑两个规则，从左到右遍历，如果当前处于递增序列，则持续增一；如果处于递减序列，则每次增加「递减序列的长度」的量。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

坑点：方法 1 要注意相邻的评分如果相等，糖果数可以任意取值，因此相等时递归就可以停止了（只需看另一边，两边都相等时直接取 1）。如果相等时仍进行递归，由于相等具有对称性，会互相递归导致死循环！

置换环贪心

置换环是线性扫描贪心中的一系列经典问题，背景是计算「使一个无重复数组有序的最小交换次数」。例如在数组 \([2,0,1,4,3]\) 中，\([2,0,1]\) 和 \([4,3]\) 分别是两个置换环，将每个置换环排序的代价是 \(length-1\)，因此将整体排序的代价就是「数组长度减去置换环的个数」。有两种做法：

将目标序列的下标用哈希表映射存储 hash[value]=index，遍历原序列，将不在位元素交换到目标位置，并使得当前位置的目标元素归位。
计算环的个数，需要将数组离散化到 \(0-N\)，标记访问过的元素，对每个未访问的元素 for(auto a: nums)，继续访问 a = nums[a]，直到绕环一周。

Todo 剑指 Offer 03. 数组中重复的数字 (E)

题目描述：一个含 \(n\) 个整数的数组，其中每个数都在区间 \([0,n-1]\) 内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

方法1：哈希表，

方法2：置换环贪心，

448. 找到所有数组中消失的数字 (E)

题目描述：一个含 \(n\) 个整数的数组，其中每个数都在区间 \([1,n]\) 内。请你找出所有在 \([1,n]\) 内但没有出现在数组中的数字。

方法1：哈希表，用一个长为 \(n\) 的数组记录每个数是否出现，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

方法2：置换环 + 原地哈希，由于原数组的长度就是 \(n\)，利用原数组哈希可以节省空间。为了不破坏数据，每次遇到一个数 a，就访问 nums[a-1]，并将 nums[a-1] 置为零表示 a 出现过。空间复杂度 \(O(1)\)。

2471. 逐层排序二叉树所需的最少操作数目 (M)

题目描述：给定一颗 \(N\) 个节点的二叉树，树上节点的取值无重复，计算将每层二叉树节点排序所需的最少交换次数。

方法1：层序遍历 + 哈希表，先遍历取出每一层的元素形成嵌套数组。对每个数组先排序得到目标序列，再用哈希表记录每个元素的目标位置（无重复），将原数组遍历并交换不在位元素，复杂度 \(O(n\log n)\)。

方法2：层序遍历 + 置换环，对每个数组先排序，再离散化，使用访问数组绕环访问，时间复杂度 \(O(n\log n)\)。

拓展：任何「取值无重复的排序所需的最少交换次数」其实就是置换环问题！

765. 情侣牵手 (H)

题目描述：n 对情侣随机坐在连续的 2n 个座位上，假设情侣对按顺序编号，第一对是 0,1，第二对是 2,3 以此类推，求最少交换座位的次数，使得每对情侣可以并肩坐在一起。

方法1：置换环 + 并查集，将数组两两分组，错误配对的情侣必然位于一个置换环，而总共需要交换的次数就是「总情侣对数 - 置换环的个数」，通过并查集找出置换环，时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(n)\)。

方法2：置换环 + BFS，将置换环视为连通分量，通过 BFS 和访问数组 \(vis\) 找出所有连通分量，时间复杂度 \(O(n)\)。

方法3：哈希表 + 贪心，用哈希表（数组）记录每个序号所在的位置，每次遍历一个情侣对，如果错误配对，则将不在位的序号交换到当前位置，并更新哈希表，可以证明每次交换都是「必要的」，时间复杂度 \(O(n)\)。

单调队列贪心

单调队列贪心是扫描贪心的一种特殊情况，需要在扫描的过程中维护一个单调递增/递减的队列。扫描的同时在队列中进行二分查找、尾部插入等操作，最终结果与队列长度、队列元素相关。

注意区分单调栈和单调队列，前者包含了栈的连续弹出操作，用来排除所有不可能成为下一个最大/最小值的元素；后者则维护一个可持续的队列（可以用数组、栈、双端队列实现）。

300. 最长递增子序列 (LIS) (M)

题目描述：一个整数数组 nums，找到其中最长严格递增子序列的长度。（子序列可以不连续）

方法1：DP，定义 \(dp[i]\) 为以 \(nums[i]\) 结尾的 LIS 长度，每次从 \(dp[j]\) 中找满足条件的最大值转移，复杂度 \(O(n^2)\)。 \[ d p[i]=\max (d p[j])+1 \text {, 其中 } 0 \leq j<i \text { 且 } n u m[j]<n u m[i] \] 方法2：贪心 + 单调队列二分查找，要使 LIS 尽可能的长，就需要让序列上升得尽可能慢，因此我们希望每次在 LIS 末尾元素尽可能的小。因此维护一个数组 \(d[i]\) 表示长度为 \(i\) 的 LIS 的末尾元素的最小值，每新来一个元素就将其二分查找到其可以放入的位置，并更新 \(d\) 数组。复杂度 \(O(n \log n)\)。

显然 \(d[i]\) 是单调严格递增的，反证：如果 \(d[i] \geqslant d[j]\) 但 \(i < j\)，则可以将 \(d[j]\) 对应的 LIS 删除 \(j-i\) 个数使其长度变为 \(i\)，但显然此时末尾元素满足 \(d[i] \geqslant d[j] \geqslant d[i]'\)，则 \(d[i]\) 与其定义相矛盾。

769. 最多能完成排序的块 (M)

题目描述：给定一个长度为 n 的数组表示 \([0, n-1]\) 的整数的一个排列。现将数组分为若干大小不等的块，并对每个块单独排序，且排序后的结果和整个数组排序的结果相同。计算数组能划分的最多块数。

方法1：贪心 + 一次遍历，由于数组是一个无重复的全排列，每个数就是其排序后对应的下标。因此维护一个变量 mx 表示已遍历过的数中的最大值（分块的上限），如果 mx 与当前遍历到的下标 i 相等，说明可以进行一次分块。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法2：贪心 + 单调队列，方法 1 要求数组是无重复的全排列，如果数字不连续、有重复就无法实现下标的对应关系。观察发现从左到右，每个分块都有一个最大值，并且这些最大值呈单调递增。因此可以用一个单调队列，时空复杂度均为 \(O(n)\)。

当栈为空，或遍历到的数 x 大于等于栈顶元素时直接入栈；
如果 x 小于栈顶元素 t，则需要把栈中大于 x 的元素弹出，再放回 t，表示「介于 x 与 t 之间」的分块融合。由于有放回的操作，所以本题实质上是单调队列而非单调栈。
最终返回栈的大小。

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

题目描述：同上一题类似，但数组大小、元素取值范围更大，且可能出现重复元素。

方法1：排序 + 哈希表，将原数组复制并排序，同时遍历两个数组，用哈希表记录出现过的元素及频次，如果在原数组出现过，则频次加一；在排序数组出现过，则频次减一。当频次为 0 时 erase 元素，如果哈希表为空，则表示划分出了一个新的块。时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。

方法2：索引排序，将原数组进行索引排序得到 \(idx\)，此时 \(idx\) 即为 \([0,n-1]\) 的全排列，因此可以用一次遍历完成。时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(\log n)\)，均为快排的开销。

方法3：贪心 + 单调队列，同上一题的方法 2，时空复杂度均为 \(O(n)\)。

239. 滑动窗口最大值 (H)

题目描述：给定一个整数数组 nums，一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。每次移动一位，返回每次滑动窗口中的最大值。

方法1：优先队列，窗口内维护一个大顶堆，每次将堆顶元素作为答案。当窗口移动时，新元素放入，旧元素懒弹出，即当旧元素成为堆顶时再弹出。因此优先队列需要放入元素值和下标，用于判断旧元素是否不在窗口内。由于队列长度最长为 \(n\)，时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。

方法2：贪心 + 单调队列，窗口内维护一个单调队列，存放可能成为下一个最大值的元素下标。因此这些下标按照从小到大的顺序被存储，并且它们对应的值是严格单调递减的。时间复杂度 \(O(n)\)，空间复杂度 \(O(k)\)。

如果队列中有两个下标，其对应的值相等或递增，后者一定比前者存在的时间更久，因此前者不可能成为最大值，可以弹出。
因此当窗口右侧进入新元素时，要先弹出比之小的所有元素。而窗口左侧的元素则在离开窗口时就可弹出。两侧都需要弹出元素，因此使用双端队列。

962. 最大宽度坡 (M)

题目描述：给定一个整数数组，定义坡是元组 (i,j)，其中 i<j 且 A[i]<=A[j]，此时坡的宽度为 j-i。求坡的最大宽度。

方法1：贪心 + 单调队列 + 二分，能成为最长子数组的左端点的元素必然构成一个递减序列，因为如果来了一个大于等于栈顶的元素，则栈顶元素一定能比新元素构成更长的区间。先正向遍历获得单调队列，再枚举每个点作为右端点，二分查找第一个满足 A[i]<=A[j] 的左端点，时间复杂度 \(O(n\log n)\)。

方法2：贪心 + 单调队列 + 栈，上述单调队列用栈实现。先正向遍历获得单调递减栈，再反向遍历枚举右端点，每遇到比栈顶更大的元素就更新答案并弹出元素，因为不会再用到。时间复杂度 \(O(n)\)。

1124. 表现良好的最长时间段 (M)

题目描述：给定一个仅包含 \(\pm 1\) 的数组，求解区间分数和大于 \(0\) 的最长区间长度。

方法1：前缀和，预处理得到前缀和之后，暴力枚举区间左右端点，时间复杂度 \(O(n^2)\)，超时。

方法2：前缀和连续性 + 哈希表，只枚举区间右端点，此时我们希望找到最小的 \(l<r\) 满足 \(pre[l]<pre[r]\)，使用哈希表记录每一个前缀和第一次出现的位置，可以优化寻找过程，时间复杂度 \(O(n)\)。

方法3：贪心 + 单调队列 + 栈，能成为最长子数组的左端点的元素必然构成一个递减序列，因为如果来了一个大于等于栈顶的元素，则栈顶元素一定能比新元素构成更长的区间。这里单调队列用栈实现。因此先正向遍历获得单调递减栈，再反向遍历枚举右端点，每遇到比栈顶更大的元素就更新答案并弹出元素。时间复杂度 \(O(n)\)。

排序贪心

56. 合并区间 (M)

题目描述：给定 N 个数堆表示若干个区间，将所有重叠的区间合并为一个大区间，返回合并后的数对集合。

方法：排序 + 贪心，将区间按照左端点排序，维护一个当前的 \(start\) 和 \(end\)，如果下一个区间左端点大于 \(end\)，则另起一个大区间；否则将其合并，更新 \(end\) 即可。时间复杂度 \(O(n\log n)\)。

646. 最长数对链 (活动安排问题) (M)

题目描述：N 个数对（第一个数字总是比第二个数字小）中，选择部分构造数对链，使得 (a,b)->(c,d) 满足 b<c。

方法1：当成 LIS 问题，也是要找一个递增序列，有 DP 和贪心 + 二分查找解法，复杂度 \(O(n^2)\) 或 \(O(n \log n)\)。

方法2：排序 + 贪心，优先挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。因此按照第二个数字排序，排序复杂度 \(O(n \log n)\)，再遍历一遍即可。

870. 优势洗牌 (M)

题目描述：给定两个大小相等的数组 nums1 和 nums2，如果 nums1 中的数大于 nums2 中相同位置的数，则具有优势，返回 num1 的一个排列，使其优势最大化。

方法1：贪心 + multiset，每次在 nums1 中寻找大于 nums2[i] 的最小值；若没有，则返回 nums1 中的最小值。为了防止重复使用，每次要在 nums1 中删除该数字且保持有序，因此采用 multiset，时间复杂度 \(O(n\log n)\)。

方法2：贪心 + 索引排序 + 对撞双指针，将两个数组都进行索引排序。每次取首个元素，如果前者大于后者，则进行配对；如果不大于，则前者和 nums2 的最大数进行配对，用双指针指向 nums2 的首尾。时间复杂度 \(O(n\log n)\)。

\(nums1\) 可以改变原有的顺序，因此可以直接在其上进行排序，不需要索引化。
但 \(nums2\) 不能改变原有的顺序，只能新建一个 \(idx\) 数组并初始化为索引序列，再自定义排序函数实现映射：
1
2
3
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j){ return nums[i] < nums[j]; });
之后就可以通过 nums2[idx[i]] 来访问升序的数组，答案也可以直接放在 nums2。

坑点：方法 1 中如果不采用 multiset 而是用排序的数组，每次删除操作的复杂度是 \(O(n)\)，整体复杂度就是 \(O(n^2)\)。

406. 根据身高重建队列 (M)

题目描述：有打乱顺序的一群人站成一个队列，每人提供两个属性：他的身高、他前面应该有多少个身高大于等于他的人。要求将这群人排回原来的顺序。

矮个子排在哪都对高个子没有影响，但是高个子排在矮个子前面就会造成影响。所以，高个子可以先排，矮个子再插队。因此要先按身高从大到小排序，身高相同再按第二关键字从小到大排序。
自定义排序：return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]);

方法：自定义排序 + 贪心，遍历排序后的数组，后来的矮个子直接插入到第二关键字的位置，能满足自身属性且不会影响到之前的队列属性，时间复杂度 \(O(n^2)\)。