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

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

题目描述：

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

贪心选择性证明：在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度变短。

• 若向内移动短板 ，水槽的短板可能变大，因此下个水槽的面积可能增大。
• 若向内移动长板 ，水槽的短板不变或变小，因此下个水槽的面积一定变小。

因此每轮向内移动短板，都会消去「不可能成为最大值的状态」。

42. 接雨水 (H)

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

方法1：暴力，对于每个坐标，其能接的水量取决于左右两边最高的柱子中较矮者，两层循环遍历，复杂度 \(O(n^2)\)。

方法2：DP 预处理最大值，两次扫描，记录每个柱子的左右两边最大值，再扫描累计，时空复杂度均为 \(O(n)\)。该方法可以简单优化：从左到右的预处理可以和第三次扫描合并，用一个变量存储左边最大值，节省一个数组。

方法3：单调不增栈 + 模拟，每遍历到一个柱子，如果小于等于栈顶元素则入栈，如果更大则说明前面的柱子可以形成水洼，则依次将所有较小数弹出，并计算栈顶元素和新柱子的距离差值（表示水洼的左右墙壁，如果此时栈空，则表示没有左墙，该水洼不成立），再把新柱子入栈。时空复杂度均为 \(O(n)\)。

方法4：贪心 + 对撞双指针，双指针从两端开始遍历，再用两个变量存储左右两边最大值，每次最值较小者向中间收窄一格，同时计算出当前柱子能接的水量（当前柱子与这一侧最值的高度差，该值就是当前柱子能接到的最大水量）。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

最值较小侧可以先计算的原因是：每个位置能接的水量取决于左右两边最高的柱子中较矮者，而最值较小侧的指针所指的位置，其所在侧的最值已经是较矮的（确定性），另一侧的最值未知但只会变得更大，所以此时该位置的答案已经可以提前确定。

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 的总数。

原创. 相邻字母不相同的最长字符串 (M)

题目描述：给定 26 个数字，分别表示字母 a-z 的数量，用这些字符拼接成相邻字母不相同的字符串，求最长字符串长度。

方法：贪心，制约总长度的关键因素在于数量最多的字符，如果它的数量比其余字符的总和多 1 个则恰好可以交错排列，否则就无法将其全部放入。其次，如果其他字符的总和超过它，则多余字符可以插进序列的前部。因此，扫描维护所有字符的总数 sum，找出最多字符数 max_cnt。如果最大值超过剩余字母数量加 1，则最长字符串长度为 2 * (sum - max_cnt) + 1。否则，可以完全利用所有字母，长度为 sum。时间复杂度 \(O(n)\)。

763. 划分字母区间

题目描述：给定一个由小写字母组成的字符串 s，将其按顺序划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

方法：贪心，由于每个字母都只可能出现在一个片段，当 s[i] 被放入当前片段后，其最后一次出现的位置就是当前片段的最短长度。因此第一次遍历收集每个字母的最后出现位置，第二次遍历时维护当前片段的最短范围 now_end，每添加一个字母就检查一次，直到 i==now_end 时一个片段结束。时间复杂度 \(O(n)\)。

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]，直到绕环一周。

// nums 中无重复元素
int getMinSwaps(vector<int>& nums) {
    unordered_map<int, int> hash;
    vector<int> sortedNums(nums);
    sort(sortedNums.begin(), sortedNums.end());
    for (int i = 0; i < sortedNums.size(); i++)
        hash[sortedNums[i]] = i;

    int cnt = 0;
    for (int i = 0; i < nums.size(); i++) {
        while(nums[i] != sortedNums[i]){
            swap(nums[i], nums[hash[nums[i]]]);
            cnt++;
        }
    }
    return cnt;
}
// 如果 nums 是 0 到 n-1 的元素，可以直接原地哈希
int getMinSwaps(vector<int>& nums) {
    int cnt = 0;
    for (int i = 0; i < nums.size(); i++) {
        while(nums[i] != i){
            swap(nums[i], nums[nums[i]]);
            cnt++;
        }
    }
    return cnt;
}

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)\)。

排序贪心

排序贪心问题通常涉及一组任务、事件或对象，需要按照某种顺序排列，目标是优化某个全局指标（如总时间、总成本、总收益等）。其核心解法是确定一个局部最优的选择顺序，最终达到全局最优。

因此，需要找到对象 A 排在对象 B 前的充分必要条件，并证明这个条件具有贪心选择性。

原创. 排队接水 (E)

题目描述：有 \(n\) 个人在一个水龙头前排队接水，数组 times 表示每个人接水所需时间，安排一个顺序使得所有人的等待时间总和最小。

直觉：让时间短的人先接水，可以减少后面人的等待时间。

证明：对于任意相邻的两个人 \(t_i<t_j\)，他们的顺序不会影响前面和后面人的等待时间。如果 \(i\) 排在 \(j\) 前，则两人的等待时间为 \(t_i+(t_i+t_j)\)，反之则为 \(t_j+(t_j+t_i)\)，显然前者更小，因此要让更小者排在前面。

方法：排序 + 贪心，按照接水时间从小到大排序，累计前缀和即可。时间复杂度 \(O(n\log n)\)。

原创. 打怪兽 (M)

题目描述：有 \(n\) 个怪兽，每个怪兽有自己的血量 HP 和它的攻击力 DPS。你可以选择其中一只，在挨了所有存活怪兽的一次攻击后攻击它。你只有 1 点攻击力，求最少会受到多少伤害。

方法：排序 + 贪心，除了要考虑到会被一只怪物打 \(DPS \times HP\) 的伤害，还要考虑到被剩余所有怪物打 \(HP\) 下，因此需要排序来减少剩余怪物的总伤害。此外，本题还有个隐含线索，就是当选中一只怪物，就必须打到底。所以就是一个贪心排序问题。时间复杂度 \(O(n\log n)\)。

直觉 1：先打 DPS 高的怪兽。反例：一个怪兽 HP 1 DPS 99，另一个怪兽 HP 100 DPS 100。如先打后者，就会被前者一直打很久。

直觉 2：先打 DPS / HP 高的怪兽。

证明：对于任意的两个相邻的怪兽 \(i\) 和 \(j\)，他们的顺序不会影响前面和后面的伤害。如果先打 \(i\) 则会受到： \[ DPS[i]\times HP[i] + DPS[j]\times (HP[i]+ HP[j]) \] 反之如果先打 \(j\) 则会受到： \[ DPS[j]\times HP[j] + DPS[i]\times (HP[i]+ HP[j]) \] 如果 \(i\) 要排在前面，则上式要小于下式，则有： \[ DPS[j] \times HP [i] < DPS[i] \times HP[j] \] 自定义排序：return i.dps * j.hp < j.dps * i.hp;

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\) 数组并初始化为索引序列，再自定义排序函数实现映射：

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)

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

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

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