排序不等式与代数全序比较器 (Exchange Sorting Greedy)¶

在许多最优化问题中，输入元素的先后排列顺序直接决定了最终的目标函数值。

这类问题的解法往往不是复杂的动态规划，而是通过微扰法（邻项交换法）推导出一个代数比较器，直接使用快速排序（\(\mathcal{O}(N \log N)\)）得到全局最优排列。

入门指引

如果您是初次接触微扰法 / 邻项交换法 (Exchange Argument)，建议先参阅基础理论与入门拆解： 👉 极简入门示例：排队打水问题与邻项交换四步法，从最直观的单服务台等待时间模型理解“局部隔离性”与代数差分推导。

1. 排序不等式 (Rearrangement Inequality) 与数学证明¶

排序不等式是序列极值问题的数学基石。

1.1 定理内容¶

设有两个同维实数序列 \(a_1 \le a_2 \le \dots \le a_n\) 与 \(b_1 \le b_2 \le \dots \le b_n\)。设 \((c_1, c_2, \dots, c_n)\) 是 \((b_1, b_2, \dots, b_n)\) 的任意置换，则恒有：

\[ \sum_{i=1}^n a_i b_{n-i+1} \le \sum_{i=1}^n a_i c_i \le \sum_{i=1}^n a_i b_i \]

即：反序和 \(\le\) 乱序和 \(\le\) 顺序和。等号当且仅当所有 \(a_i\) 相等或所有 \(b_i\) 相等时成立。

1.2 微扰法证明¶

采用微扰法（邻项交换法）：

假设当前排列中存在一对相邻逆序项：\(a_j < a_{j+1}\) 但 \(c_j > c_{j+1}\)；
我们将 \(c_j\) 与 \(c_{j+1}\) 交换位置，形成新排列；
计算交换前后的内积差值：

\[ \Delta = (a_j c_{j+1} + a_{j+1} c_j) - (a_j c_j + a_{j+1} c_{j+1}) = (a_{j+1} - a_j)(c_j - c_{j+1}) > 0 \]

因为 \(a_{j+1} - a_j > 0\) 且 \(c_j - c_{j+1} > 0\)，差值严格为正，说明每一次消除逆序对的交换都会使总和严格变大；
经过有限次冒泡交换消除所有逆序对后，必定达到全顺序排列，此时乘积和取得全局最大值。

2. 经典模型与代数比较器推导¶

2.1 字符串拼接最大数 (LeetCode 179)¶

问题：给定非负整数数组，重排使得拼成的数值最大。例如 [3, 30, 34, 5, 9] 拼成 "9534330"。

微扰与比较器设计：¶

定义两个字符串 \(a\) 与 \(b\) 之间的二元关系 \(\succ\)：

\[ a \succ b \iff a \circ b > b \circ a \]

（其中 \(\circ\) 表示字符串拼接，比较按十进制大数字典序/数值大小进行）。

贪心策略：使用该比较规则对所有数字字符串进行降序排序。

步骤一：严格弱序与传递性代数证明（为什么可以排序？）¶

为了使基于比较的排序算法（如 std::sort）行为合法且确定，二元关系 \(\succ\) 必须构成严格弱序（Strict Weak Ordering）：

非自反性 (Irreflexivity)：\(a \not\succ a\)。
- 显然 \(a \circ a = a \circ a\)，不满足严格大于，成立。
非对称性 (Asymmetry)：若 \(a \succ b\)，则 \(b \not\succ a\)。
- 若 \(a \circ b > b \circ a\)，则显然不可能有 \(b \circ a > a \circ b\)，成立。
传递性 (Transitivity)：若 \(a \succ b\) 且 \(b \succ c\)，则必有 \(a \succ c\)。

实数标量映射证明传递性

设数字字符串 \(X\) 的十进制位数为 \(l(X)\)，其对应的十进制数值为 \(v(X)\)。拼接字符串 \(a \circ b\) 的数值等价于 \(v(a) \cdot 10^{l(b)} + v(b)\)。

条件 \(a \succ b \iff a \circ b > b \circ a\) 在代数上等价于：

\[ v(a) \cdot 10^{l(b)} + v(b) > v(b) \cdot 10^{l(a)} + v(a) \iff v(a)(10^{l(b)} - 1) > v(b)(10^{l(a)} - 1) \]

两边同时除以 \((10^{l(a)} - 1)(10^{l(b)} - 1) > 0\)，得到：

\[ \frac{v(a)}{10^{l(a)} - 1} > \frac{v(b)}{10^{l(b)} - 1} \]

定义实数标量映射函数：

\[ f(X) = \frac{v(X)}{10^{l(X)} - 1} \]

则比较规则 \(a \succ b\) 等价于实数标量的大小比较：\(f(a) > f(b)\)。由于实数域上的严格大于关系天然具备自反性、反对称性与严格传递性（\(f(a) > f(b) \land f(b) > f(c) \implies f(a) > f(c)\)），因此该比较规则构成了严格的全序关系！任何输入数组都能排成唯一的降序序列 \(s_1 \succeq s_2 \succeq \dots \succeq s_n\)。

步骤二：全局最优性证明（邻项交换法 Exchange Argument / 反证法）¶

我们通过反证法证明：贪心排序得到的序列拼接成的数字串是所有排列中全局最大的。

反证假设：假设贪心排序序列 \(S = [s_1, s_2, \dots, s_n]\) 不是最大数，则必然存在另一个排列 \(O = [o_1, o_2, \dots, o_n]\) 是真正的全局最优解，且 \(O\) 中至少存在一对元素不满足贪心序。
寻找相邻逆序对：根据排列逆序数性质，在非贪心序排列 \(O\) 中，必然存在至少一对相邻元素 \((o_i, o_{i+1})\) 满足局部逆序：

\[ o_{i+1} \succ o_i \iff o_{i+1} \circ o_i > o_i \circ o_{i+1} \]

局部邻项交换微扰：构造新排列 \(O'\)，仅交换 \(o_i\) 与 \(o_{i+1}\) 的位置，其余元素位置保持不变：
- 设前缀 \(A = o_1 \circ \dots \circ o_{i-1}\)，后缀 \(B = o_{i+2} \circ \dots \circ o_n\)；
- 原排列数值为：\(val(O) = A \circ (o_i \circ o_{i+1}) \circ B\)；
- 新排列数值为：\(val(O') = A \circ (o_{i+1} \circ o_i) \circ B\)。
差值展开计算：设后缀 \(B\) 的十进制总字符长度为 \(L_B\)。将 \(val(O)\) 与 \(val(O')\) 代数展开：

\[ val(O) = A \cdot 10^{l(o_i) + l(o_{i+1}) + L_B} + (o_i \circ o_{i+1}) \cdot 10^{L_B} + B \]

\[ val(O') = A \cdot 10^{l(o_{i+1}) + l(o_i) + L_B} + (o_{i+1} \circ o_i) \cdot 10^{L_B} + B \]

由于 $l(o_i) + l(o_{i+1}) = l(o_{i+1}) + l(o_i)$，两式相减后前缀项与后缀项完全相互抵消：

\[ val(O') - val(O) = \left[(o_{i+1} \circ o_i) - (o_i \circ o_{i+1})\right] \times 10^{L_B} \]

导出矛盾：由已知条件 \(o_{i+1} \succ o_i \iff o_{i+1} \circ o_i > o_i \circ o_{i+1}\)，因此：

\[ val(O') - val(O) > 0 \implies val(O') > val(O) \]

这表明交换相邻逆序对后，得到的新序列 $O'$ 比原假设的最优解 $O$ 严格更大，发生矛盾！
任何非贪心序列均可通过有限次相邻交换逐步消除逆序对转化为贪心序列 $S$，且每次交换均使总数值严格单调递增。因此，**贪心排序序列 $S$ 必为全局最大数**。证毕。

#include <vector>
#include <string>
#include <algorithm>

std::string largestNumber(std::vector<int>& nums) {
    std::vector<std::string> str_nums;
    str_nums.reserve(nums.size());
    for (int x : nums) {
        str_nums.push_back(std::to_string(x));
    }

    // 严格全序比较器
    std::sort(str_nums.begin(), str_nums.end(), [](const std::string& a, const std::string& b) {
        return a + b > b + a;
    });

    // 边界特判: 最高位为 '0' 说明全为 0
    if (str_nums[0] == "0") return "0";

    std::string result;
    for (const auto& s : str_nums) {
        result += s;
    }
    return result;
}

2.2 单机调度与加权完工时间最小化 (Smith's Rule / WSPT)¶

2.2.1 理论渊源与经典问题形式化¶

Smith's Rule（史密斯法则） 由 Wayne E. Smith 于 1956 年在其经典论文中提出，在运筹学与调度理论（Scheduling Theory）中也被广泛称为 WSPT（Weighted Shortest Processing Time first，加权最短处理时间优先）。在经典的 Graham 三元组调度记号中，该问题被记为：

\[ 1 \mid \mid \sum w_i C_i \]

机器环境：只有 \(1\) 台机器，同一时刻只能连续处理一个任务，不可抢占（Non-preemptive）；
任务集合：给定 \(n\) 个任务，每个任务有确定性的处理时间 \(p_i > 0\) 和权重 / 惩罚速率 \(w_i > 0\)；
完工时间：设任务 \(i\) 在当前调度方案下的完成时刻为 \(C_i\)；
优化目标：寻找任务的一个全局最优排列 \(p = (p_1, p_2, \dots, p_n)\)，最小化所有任务的加权完工时间总和：

\[ \min \sum_{i=1}^n w_i C_i \]

2.2.2 邻项微扰法 (Exchange Argument) 严格代数推导¶

考虑任意调度方案中相邻处理的两个任务 \(A\) 与 \(B\)（设 \(A\) 在第 \(k\) 位，\(B\) 紧排在第 \(k+1\) 位）。设排在 \(A\) 之前的所有前置任务的总耗时为 \(T_{pre} = \sum_{j=1}^{k-1} p_j\)。

方案一（\(A\) 在前，\(B\) 在后）：
\(A\) 的完工时间：\(C_A = T_{pre} + p_A\)
\(B\) 的完工时间：\(C_B = T_{pre} + p_A + p_B\)
局部加权代价贡献：

\[ \operatorname{Cost}_1 = w_A (T_{pre} + p_A) + w_B (T_{pre} + p_A + p_B) \]

方案二（\(B\) 在前，\(A\) 在后）：
根据邻项交换的局部隔离性，\(A\) 之前与 \(B\) 之后的所有任务的完工时间完全不受影响；
\(B\) 的完工时间：\(C'_B = T_{pre} + p_B\)
\(A\) 的完工时间：\(C'_A = T_{pre} + p_B + p_A\)
局部加权代价贡献：

\[ \operatorname{Cost}_2 = w_B (T_{pre} + p_B) + w_A (T_{pre} + p_B + p_A) \]

代数差分展开：

\[ \operatorname{Cost}_1 - \operatorname{Cost}_2 = \big[w_A(T_{pre} + p_A) + w_B(T_{pre} + p_A + p_B)\big] - \big[w_B(T_{pre} + p_B) + w_A(T_{pre} + p_B + p_A)\big] \]

展开后公共项 \((w_A + w_B) T_{pre} + w_A p_A + w_B p_B\) 完全抵消，仅剩：

\[ \operatorname{Cost}_1 - \operatorname{Cost}_2 = w_B p_A - w_A p_B \]

导出最优性判定准则：若方案一严格优于方案二（即 \(\operatorname{Cost}_1 < \operatorname{Cost}_2\)），必须且仅须：

\[ w_B p_A - w_A p_B < 0 \iff w_B p_A < w_A p_B \iff \frac{w_A}{p_A} > \frac{w_B}{p_B} \]

定理结论（Smith's Rule）：将所有任务按照 性价比密度 \(\rho_i = \frac{w_i}{p_i}\) 从大到小降序排列（或按 \(\frac{p_i}{w_i}\) 升序排列），所得调度方案必然是全局最优解！

2.2.3 物理直觉与经典退化模型¶

密度视角（Density View）：\(\frac{w_i}{p_i}\) 代表“单位处理时间内所消灭的延迟惩罚速率”。贪心原则要求我们以最高效率优先消灭那些“性价比最高（惩罚大、耗时短）”的任务。
特例一（所有权重相同 \(w_i = 1\)）：退化为经典 排队打水问题 / 最短处理时间优先 (SPT / SJF)，按 \(p_i\) 升序排列。
特例二（所有耗时相同 \(p_i = 1\)）：退化为 最大权重优先，按 \(w_i\) 降序排列。

2.2.4 工业级 C++ 比较器实现要点¶

在工程和算法竞赛中，直接使用浮点除法 (double)w_a / p_a > (double)w_b / p_b 会受到浮点精度丢失的影响。标准做法是使用交叉相乘法（Cross Multiplication），并转为 64 位整数防溢出：

// 严格弱序交叉相乘比较器
std::sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
    return 1LL * a.w * b.p > 1LL * b.w * a.p;
});

3. LeetCode 经典真题精选与深度精析¶

LeetCode 179 - 最大数 (Largest Number) 中等
提示

自定义全序比较器微扰排序（严格弱序传递性 + 邻项交换最优性证明）。
- 比较规则：定义 \(a \succ b \iff a + b > b + a\)。
- 传递性证明：将数字字符串映射为实数标量 \(f(x) = \frac{x}{10^{len(x)} - 1}\)，由实数域全序性证明 \(a \succ b \land b \succ c \implies a \succ c\)（详见本文 2.1 节）。
- 全局最优性证明：采用邻项交换法（Exchange Argument）。假设存在非贪心最优解，必含相邻逆序对 \((o_i, o_{i+1})\)，交换后差值 \([(o_{i+1} \circ o_i) - (o_i \circ o_{i+1})] \times 10^{L_B} > 0\)，导出矛盾。
- 边界特判：排序后若最高位为 "0"，说明整个数组全为 0，直接返回 "0"。
- 时间复杂度 \(\mathcal{O}(N \log N \cdot L)\)，空间复杂度 \(\mathcal{O}(N \cdot L)\)。
LeetCode 406 - 根据身高重建队列 (Queue Reconstruction by Height) 中等
提示

高个子先入为主的降序插入贪心。
- 核心洞察：矮个子的插入位置，完全不会影响高个子的相对排名（因为高个子只关注 \(\ge\) 自身身高的人数）。
- 排序规则：按身高 \(h\) 降序排序；若身高相同，按前面人数 \(k\) 升序排序。
- 贪心插入：排好序后，依次将每个人插入到其对应的下标 \(k\) 位置（result.insert(result.begin() + k, person)）。
- 每次插入时，前面已在数组中的人全部都比当前人高，当前人插入在第 \(k\) 个位置恰好满足其前面有 \(k\) 个更高的人。时间复杂度 \(\mathcal{O}(N^2)\)。
LeetCode 670 - 最大交换 (Maximum Swap) 中等
提示

低位最大数字前移贪心。
- 只能交换一次。想要让数值最大，应尽可能让数值更大且出现在越靠后（低位）的数字，与越靠前（高位）且数值较小的数字交换。
- 倒序记录每个数字 \(0 \sim 9\) 最后一次出现的下标 last_pos[digit]。
- 从高位到低位扫描每一位数字 \(nums[i]\)，枚举所有比它大的可能数字 \(d \in [9, nums[i] + 1]\)：
- 若存在 \(last\_pos[d] > i\)，说明在 \(i\) 后面有一个更大的数字 \(d\)，直接交换并立即返回结果！
- 时间复杂度 \(\mathcal{O}(N)\)，额外空间 \(\mathcal{O}(1)\)。
LeetCode 1005 - K 次取反后最大化的数组和 (Maximize Sum Of Array After K Negations) 简单
提示

绝对值优先反转贪心。
- 按绝对值大小降序排序。
- 遍历数组：若当前数为负数且 \(k > 0\)，贪心地将其翻转为正数，同时 \(k--\)。
- 若遍历完后 \(k\) 仍大于 0 且为奇数（偶数次取反可以相互抵消不改变值），则贪心地将数组中绝对值最小的那个数（数组末尾元素）翻转一次。
- 时间复杂度 \(\mathcal{O}(N \log N)\)。
LeetCode 621 - 任务调度器 (Task Scheduler) 中等
提示

最高频任务桶排布与贪心构造公式。
- 相同任务之间必须至少间隔 \(n\) 个冷却周期。
- 桶构造贪心：
- 设出现次数最多的任务执行了 \(max\_count\) 次，且频次同为 \(max\_count\) 的任务种类数为 \(count\_max\)；
- 这些最高频任务构成 \((max\_count - 1)\) 个框架桶，每个桶长度为 \((n + 1)\)，最后一个桶只包含 \(count\_max\) 个任务；
- 所需最短时间公式为：\(\operatorname{Total} = \max\Big(\operatorname{tasks.size()}, (max\_count - 1) \times (n + 1) + count\_max\Big)\)。
- 剩余其他任务可以自由填充在各个桶的空隙中，若空隙填满，只需横向拉长桶即可，绝不会增加额外空闲时间。时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(|\Sigma|)\)。
LeetCode 767 - 重构字符串 (Reorganize String) 中等
提示

鸽巢原理上限检验 + 大顶堆/隔位交替贪心。
- 使得相邻字符互不相同。
- 鸽巢原理：若某个字符频次 \(max\_count > \lceil n / 2 \rceil\)，根据抽屉原理必定存在相邻重复，直接返回空串 ""。
- 贪心策略一（大顶堆）：
- 优先队列按字符剩余频次维护大顶堆；
- 每次弹出频次最多的两个不同字符拼接，频次减 1 后重新入堆，保证高频字符尽可能被快速交替消耗。
- 贪心策略二（隔位交替填入）：
- 优先将最高频字符填在所有偶数下标 \(0, 2, 4, \dots\)；
- 随后将其余字符依次填入剩余偶数位和奇数位，时间复杂度 \(\mathcal{O}(N)\)。
LeetCode 1405 - 最长快乐字符串 (Longest Happy String) 中等
提示

多路大顶堆贪心 + 避免连续三相同分支选择。
- 字符不能连续出现 3 次。
- 用大顶堆维护当前剩余次数最多的字符二元组 (count, char)。
- 每次贪心取出剩余次数最多的字符：
- 若当前字符串末尾两个字符与该字符相同（即将违反连续 3 次规则），则不能选它，转而从堆中取出次多字符填入 1 次；
- 否则，安全填入当前最多字符 1 次；
- 将更新后的字符次数重新压入堆，直至堆为空或无法再填入任何字符。时间复杂度 \(\mathcal{O}(A + B + C)\)。
LeetCode 3273 - 对 Bob 造成伤害的最小时间 (Minimum Amount of Damage Dealt to Bob) 中等
提示

Smith's Rule（加权最短处理时间优先 WSPT）1:1 原型题。
- 模型映射：
- Bob 每次攻击造成 power 点伤害，击杀敌人 \(i\) 所需时间为 \(p_i = \lceil \text{health}[i] / \text{power} \rceil\)；
- 敌人 \(i\) 存活期间每秒对 Bob 造成 \(w_i = \text{damage}[i]\) 点伤害；
- 敌人 \(i\) 在时刻 \(C_i\) 被消灭，其贡献的受击伤害为 \(w_i \cdot C_i\)；总伤害为 \(\sum_{i=1}^n w_i C_i\)。
- 比较器推导：
- 对比相邻敌人 \(A\) 和 \(B\)：先打 \(A\) 产生附加伤害 \(p_A \cdot w_B\)，先打 \(B\) 产生附加伤害 \(p_B \cdot w_A\)；
- 先打 \(A\) 优于先打 \(B\) 当且仅当 \(p_A \cdot w_B < p_B \cdot w_A \iff \frac{w_A}{p_A} > \frac{w_B}{p_B}\)；
- 严格等价于 Smith's Rule：按性价比 \(\frac{\text{damage}[i]}{p_i}\) 降序排列。
- 防溢出与交叉相乘：使用 1LL * damage[a] * p[b] > 1LL * damage[b] * p[a] 避免浮点精度损失与整数溢出。
- 时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(N)\)。
LeetCode 2136 - 全部开花的最早一天 (Earliest Possible Day of Full Bloom) 困难
提示

并行重叠调度中的邻项交换法 (Johnson's Rule 思想)。
- 核心洞察：
- 所有花的播种时间 plantTime 必须串行占用工人（总和恒为 \(\sum plantTime[i]\)）；
- 但各花的生长过程 growTime 是完全并行、互不干扰的；
- 开花时间由“播种结束时刻 + 生长时长”决定。
- 微扰分析：
- 设相邻两株花 \(A\) 与 \(B\)：
  - 先播种 \(A\) 再播种 \(B\)，最终开花时间瓶颈为 \(\max(p_A + g_A, p_A + p_B + g_B)\)；
  - 先播种 \(B\) 再播种 \(A\)，最终开花时间瓶颈为 \(\max(p_B + g_B, p_B + p_A + g_A)\)；
- 对比两式的瓶颈关键项：\(p_A + p_B + g_B\) 与 \(p_B + p_A + g_A\)，消去公共前缀 \(p_A + p_B\) 后，直接等价于比较 \(g_B\) 与 \(g_A\)；
- 先播种 \(A\) 更优当且仅当 \(g_A > g_B\)。
- 结论：生长周期越长（growTime 越大）的花必须越早播种，按 growTime 降序排序即可。
- 时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(N)\)。
LeetCode 1665 - 完成所有任务的最少初始能量 (Minimum Initial Energy to Finish Tasks) 困难
提示

门槛与消耗解耦的邻项交换微扰贪心与全序比较。

1. 模型分析与物理直觉¶

每个任务 \(i\) 具有两个属性：实际消耗 \(actual[i]\) 与启动门槛 \(minimum[i]\)（题目保证 \(minimum[i] \ge actual[i]\)）。
- 启动门槛（保证金）：必须至少拥有 \(minimum[i]\) 能量才允许开始该任务；
- 实际消耗（净支出）：任务完成后只扣除 \(actual[i]\)；
- 富余保证金（净退税）：任务执行完成后，未被实际消耗的“富余量”为 \(d_i = minimum[i] - actual[i] \ge 0\)。
物理直觉：富余量 \(d_i\) 越大的任务，其门槛虽高，但实际净消耗少，完成后剩余的能量越多。如果将富余量大的任务排在最前面，其高额的“门槛保证金”在任务完成后能作为后续任务的“垫底资金”继续复用，从而最大化资金流转效率。

2. 邻项交换法 (Exchange Argument) 严格数学推导¶

设排列中存在相邻两项任务 \(A = (a_A, m_A)\) 与 \(B = (a_B, m_B)\)，其中 \(a\) 为实际消耗 \(actual\)，\(m\) 为启动门槛 \(minimum\)。
- 局部微扰的独立性：
- 处理 \(A, B\) 之前，前置任务累计消耗的能量固定为 \(S_{pre}\)；
- 无论先执行 \(A\) 还是先执行 \(B\)，完成这两项任务后的累计总净消耗恒为 \(a_A + a_B\)；
- 因此，后续所有任务所需的剩余能量完全不受 \(A\) 与 \(B\) 相对顺序的影响。优化目标完全退化为：使得执行这两项任务所需的局部起始能量最小。
- 两类顺序的局部能量需求：
- 顺序一（先做 \(A\)，后做 \(B\)）：启动 \(A\) 需至少 \(m_A\)；完成 \(A\) 消耗 \(a_A\) 后，剩余能量需满足 \(B\) 的门槛 \(m_B\)，即初始需满足 \(a_A + m_B\)。故局部所需初始能量为 \(Req(A, B) = \max(m_A, a_A + m_B)\)；
- 顺序二（先做 \(B\)，后做 \(A\)）：同理，局部所需初始能量为 \(Req(B, A) = \max(m_B, a_B + m_A)\)。
- 代数变形与比较准则求解：
- 要判定何时 \(Req(A, B) \le Req(B, A)\)，在不等式两边同时减去 \((a_A + a_B)\)：\(\max(m_A - a_A - a_B, m_B - a_B) \le \max(m_B - a_B - a_A, m_A - a_A)\)。
- 令 \(x = m_A - a_A \ge 0\)，\(y = m_B - a_B \ge 0\)，上式化简为：\(\max(x - a_B, y) \le \max(y - a_A, x)\)。
- 由于实际消耗 \(a_A > 0, a_B > 0\)：
  - 若 \(x > y\)：右式中 \(y - a_A < y < x\)，故右式等于 \(x\)；左式中由于 \(a_B > 0 \implies x - a_B < x\)，且已知 \(y < x\)，故左式两项均严格小于 \(x\)。因此 \(\max(x - a_B, y) < x = \text{RHS}\)，严格满足 \(Req(A, B) < Req(B, A)\)！
  - 若 \(x = y\)：两式对称，交换顺序不改变所需能量。
- 推导结论：先做 \(A\) 优于先做 \(B\) 当且仅当 \(m_A - a_A > m_B - a_B\)。即：严格按 \((minimum[i] - actual[i])\) 从大到小降序排列，得到的序列必然是全局最优解！
3. 两种代码实现方案¶

方案一：正向贪心模拟（维护当前电量与初始总电量）¶
```
class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        // 按 (minimum - actual) 降序排序
        sort(tasks.begin(), tasks.end(), [](const auto& a, const auto& b) {
            return (a[1] - a[0]) > (b[1] - b[0]);
        });

        int ans = 0; // 最少初始总能量
        int cur = 0; // 当前拥有的能量

        for (const auto& t : tasks) {
            int actual = t[0], minimum = t[1];
            // 若当前能量不足以启动该任务，必须在初始时追加差额
            if (cur < minimum) {
                ans += (minimum - cur);
                cur = minimum;
            }
            cur -= actual;
        }
        return ans;
    }
};
```
方案二：逆向递推（从终点 0 能量倒推初始能量）¶

任务全部完成后的最理想状态是剩余能量恰好为 \(0\)。从最后一个任务逆向倒推：若完成任务 \(i\) 后需要保留 \(E_{next}\) 能量，则执行任务 \(i\) 之前必须拥有 \(\max(minimum_i, E_{next} + actual_i)\) 能量。
```
class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [](const auto& a, const auto& b) {
            return (a[1] - a[0]) > (b[1] - b[0]);
        });

        int cur = 0; // 终点剩余能量为 0
        for (int i = (int)tasks.size() - 1; i >= 0; --i) {
            cur = max(tasks[i][1], cur + tasks[i][0]);
        }
        return cur;
    }
};
```
4. 复杂度分析¶
- 时间复杂度：\(\mathcal{O}(N \log N)\)，排序耗时 \(\mathcal{O}(N \log N)\)，后续正向/逆向线性扫描仅需 \(\mathcal{O}(N)\)。
- 空间复杂度：\(\mathcal{O}(1)\)（原地排序）或 \(\mathcal{O}(\log N)\) 排序调用栈空间。