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

本文最后更新于:2023年2月22日 下午

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

题目描述

方法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)$。

方法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,表示「介于 xt 之间」的分块融合。由于有放回的操作,所以本题实质上是单调队列而非单调栈。

最终返回栈的大小。

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<jA[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)

题目描述:给定两个大小相等的数组 nums1nums2,如果 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)$。

2449. 使数组相似的最少操作次数 (H)

题目描述:给定长度相等的两个数组 numstarget,操作 nums,使其与 target 中每个元素出现次数相等,但位置可以不同。每次操作需选中两个数,其中一个数 $+2$,另一个数 $-2$。计算最少操作次数。

方法:排序 + 贪心,要使操作次数最小化,可以证明应该让最小的一对、次小的一对、以此类推。由于 $\pm 2$ 不会改变奇偶性,因此配对时考虑奇偶数分离,再进行排序。累加每对元素的差的绝对值,时间复杂度 $O(n\log n)$。

坑点:本题保证能使两个数组相似,因此最终累加的结果除以 $4$ 一定能得到整数。


力扣刷题笔记 #07 贪心算法
https://hwcoder.top/LeetCode-Greedy
作者
Wei He
发布于
2022年10月2日
许可协议