股票与序列贪心：多次交易、加油站与柠檬水找零

摘要

本文深入剖析四道形态各异的贪心题：LeetCode 122（买卖股票的最佳时机 II，峰谷累积策略）、LeetCode 134（加油站，环形差分贪心）、LeetCode 860（柠檬水找零，模拟优先级贪心）、LeetCode 406（根据身高重建队列，构造类贪心）。这四道题没有统一的”公式”，但都遵循一个共同主线：局部最优与全局最优的等价性。每道题的核心是找到那个”局部贪心选择不会损害全局最优”的关键性质，并以交换论证或直觉等价性来论证正确性。

第 1 章 LeetCode 122：买卖股票的最佳时机 II

1.1 题目

LeetCode 122 - Best Time to Buy and Sell Stock II（中等）

给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 利润 = 5-1 = 4
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 6 天（股票价格 = 6）的时候卖出, 利润 = 6-3 = 3
     总利润 = 4 + 3 = 7

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）买入，在第 5 天（股票价格 = 5）卖出，利润 = 5 - 1 = 4

1.2 峰谷策略的直觉

第一个直觉：找所有的”低谷买入，高峰卖出”的机会。但确定”局部低谷”和”局部高峰”需要向后看，实现起来麻烦。

关键等价简化：设 $d_{i} = prices [i] - prices [i - 1]$ （相邻两天的价差）。

任意一段”从第 $a$ 天买入，第 $b$ 天卖出”的利润 = $prices [b] - prices [a] = \sum_{i = a + 1}^{b} d_{i}$ 。

因此，总利润 = 所有被选择的”收益段”的正价差之和。由于每天可以先卖后买，任意分割都合法，所以把所有正价差都纳入收益就是最优策略。

$最大利润 = \sum_{i = 1}^{n - 1} max (0, prices [i] - prices [i - 1])$

1.3 贪心实现

public int maxProfit(int[] prices) {
    int profit = 0;
 
    for (int i = 1; i < prices.length; i++) {
        // 只要今天比昨天贵，就"等价于"昨天买今天卖
        // 这等价于把所有上涨的价差都纳入收益
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
 
    return profit;
}

时间复杂度： $O (n)$ ，空间 $O (1)$ 。

1.4 正确性证明

命题：上述贪心给出最大利润。

证明：设最优策略的买入卖出序列为 $a_{1} < b_{1} < a_{2} < b_{2} < ... < a_{k} < b_{k}$ ，最优利润为：

$OPT = \sum_{j = 1}^{k} (prices [b_{j}] - prices [a_{j}]) = \sum_{j = 1}^{k} \sum_{i = a_{j} + 1}^{b_{j}} d_{i}$

其中只包含正的 $d_{i}$ （只有上涨段才值得交易）和部分正的 $d_{i}$ （最优可能跨越某些下跌段，但总和仍然最大）。

贪心的利润是 $GRD = \sum_{i : d_{i} > 0} d_{i}$ ，即所有正价差之和。

显然 $OPT \leq GRD$ （因为 OPT 可能遗漏了某些正 $d_{i}$ ，或包含了某些负 $d_{i}$ ）。

又因为 $GRD$ 对应一个合法的交易策略（每个正 $d_{i}$ 对应前一天买当天卖，可以同一天先卖后买），所以 $GRD \leq OPT$ 。

因此 $OPT = GRD$ ，贪心给出最优解。

第 2 章 LeetCode 134：加油站

2.1 题目

LeetCode 134 - Gas Station（中等）

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。如果存在解，则保证它是唯一的。

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1

2.2 核心定理

设 $diff [i] = gas [i] - cost [i]$ （在第 $i$ 站净获得的油量）。

定理 1：如果 $\sum_{i} diff [i] \geq 0$ ，则一定存在可行的出发站。

证明：假设总量 $\geq 0$ ，考虑从站 0 出发，记录每走一步后的油箱前缀和 $S [k] = \sum_{i = 0}^{k - 1} diff [i]$ 。设 $S [m]$ 是所有前缀和中最小的。从站 $m$ 出发，走到任意位置 $k > m$ 时，油箱 = $\sum_{i = m}^{k - 1} diff [i] = S [k] - S [m] \geq 0$ （因为 $S [m]$ 是最小前缀和）。走完前半段（从 $m$ 到 $n - 1$ ）后回到 $m$ ，此时油箱 = $S [n] - S [m]$ ，继续走后半段（从 $0$ 到 $m - 1$ ）时，油箱变化量是 $S [m] - S [0] = S [m]$ （因 $S [0] = 0$ ），结束时油箱 = $S [n] - S [m] + S [m] = S [n] \geq 0$ 。全程油箱非负，可行。

定理 2：如果 $\sum_{i} diff [i] < 0$ ，则不存在可行出发站。

证明：显然，绕一圈净消耗量为 $- \sum_{i} diff [i] > 0$ ，油箱从 0 出发不可能回到非负。

2.3 贪心：线性找起始点

定理 1 的证明实际上给出了一个算法：找 $\sum_{i} diff [i]$ 最小时对应的下一个位置。但有更简洁的线性贪心：

观察：从站 $s$ 出发，依次经过 $s, s + 1, ..., k$ ，如果在某个位置 $k$ 处油箱变负（即 $\sum_{i = s}^{k} diff [i] < 0$ ），则 $s, s + 1, ..., k$ 中的任何站都不能作为起始站。

原因：若从 $j \in [s, k]$ 出发，走到 $k$ 时的油量 = $\sum_{i = j}^{k} diff [i]$ 。由于 $\sum_{i = s}^{j - 1} diff [i] \geq 0$ （从 $s$ 到 $j - 1$ 油量非负，否则在 $j - 1$ 前已失败），所以 $\sum_{i = j}^{k} diff [i] \leq \sum_{i = s}^{k} diff [i] < 0$ ，即从 $j$ 出发也会在 $k$ 失败。

贪心策略：从站 0 出发模拟，遇到油量变负时，将起始站更新为下一站，并重置油量为 0。同时记录总油量，最后验证是否可行。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalTank = 0;    // 总净油量（决定是否有解）
    int currentTank = 0;  // 从当前 start 出发的累积净油量
    int start = 0;        // 候选起始站
 
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        totalTank += diff;
        currentTank += diff;
 
        // 如果从 start 出发到 i 时油量变负，
        // 说明 [start, i] 中的任何站都不能作为起始站
        if (currentTank < 0) {
            start = i + 1;    // 新的候选起始站是下一站
            currentTank = 0;  // 重置累积油量
        }
    }
 
    // 如果总净油量 >= 0，则 start 就是答案；否则无解
    return totalTank >= 0 ? start : -1;
}

为什么最后的 start 就是答案：根据上面的分析，一旦 currentTank 变负，[start, i] 中所有站都不可行，下一个可行起始站只能是 i+1 或更后。循环完后，start 是”最后一次重置后”的起始站，也就是”所有不可行段之后”的第一个站，恰好是满足定理 1 中”最小前缀和之后的站”的位置。

2.4 手工演示

gas = [1,2,3,4,5], cost = [3,4,5,1,2], diff = [-2,-2,-2,3,3]

i	diff	currentTank	totalTank	操作
0	-2	-2	-2	currentTank<0，start=1, currentTank=0
1	-2	-2	-4	currentTank<0，start=2, currentTank=0
2	-2	-2	-6	currentTank<0，start=3, currentTank=0
3	3	3	-3	正常
4	3	6	0	正常

totalTank = 0 >= 0，返回 start = 3。正确！

第 3 章 LeetCode 860：柠檬水找零

3.1 题目

LeetCode 860 - Lemonade Change（简单）

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills，其中 bills[i] 是第 i 位顾客付的账单。如果你能给每位顾客正确找零，返回 true，否则返回 false。

输入: bills = [5,5,5,10,20]
输出: true
输入: bills = [5,5,10,10,20]
输出: false

3.2 贪心分析

顾客只会付 5、10、20 三种面额，找零情形分析：

顾客付款	找零金额	找零方式
5 美元	0	无需找零，收入一张 5 美元
10 美元	5	找一张 5 美元
20 美元	15	方案 A：一张 10 美元 + 一张 5 美元；方案 B：三张 5 美元

关键贪心：当顾客付 20 美元时，优先选择方案 A（10+5），而非方案 B（三个 5）。

原因（交换论证思路）：5 美元比 10 美元”更通用”——遇到付 10 美元的顾客，只能用 5 美元找零，不能用 10 美元；但遇到付 20 美元的顾客，可以用 10 美元代替两张 5 美元。因此，5 美元更稀缺，应该优先保留。当有 10 美元时，优先用 10 美元找 20 美元的零，节省 5 美元供更紧迫的场景使用。

public boolean lemonadeChange(int[] bills) {
    int fives = 0;   // 手头的 5 美元数量
    int tens = 0;    // 手头的 10 美元数量
    // 不需要记录 20 美元，因为 20 美元只收不找
 
    for (int bill : bills) {
        if (bill == 5) {
            fives++;           // 直接收入
        } else if (bill == 10) {
            if (fives == 0) return false;  // 没有 5 美元可找
            fives--;
            tens++;
        } else {  // bill == 20
            // 优先用 10 + 5，保留更通用的 5 美元
            if (tens > 0 && fives > 0) {
                tens--;
                fives--;
            } else if (fives >= 3) {
                fives -= 3;
            } else {
                return false;  // 无法找零
            }
        }
    }
 
    return true;
}

3.3 柠檬水贪心的适用性

这道题的贪心策略成立，是因为”优先级关系”满足传递性：5 美元比 10 美元更稀缺（用途更广），所以在等价方案之间选择”保留稀缺资源”的方案不会使情况更差。

这类”保留稀缺资源”的贪心模式在找零、任务调度、资源分配中频繁出现。

第 4 章 LeetCode 406：根据身高重建队列

4.1 题目

LeetCode 406 - Queue Reconstruction by Height（中等）

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue，其中 queue[j] = [hj, kj] 是队列中第 $j$ 个人的属性（queue[0] 是排在队列前面的人）。

输入: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

4.2 排序方向设计

这道题是”构造类贪心”——通过特定的插入顺序，保证最终结果满足所有约束。

关键洞察：高个子先插入，矮个子不影响高个子前面的计数（因为矮个子不满足”身高大于等于”高个子的条件）。

排序规则：

按身高降序（高的先处理）
身高相同时，按 k 值升序（k 小的先处理）

贪心步骤：对排序后的每个人 [h, k]，将其插入到当前已建队列的第 k 个位置（下标为 k）。

为什么这是正确的：

高个子先插入，插入位置 k 意味着前面有 k 个人——因为此时队列里只有身高 >= h 的人，所以前面恰好有 k 个满足条件的人。
矮个子后插入，不影响高个子的相对顺序和计数（矮个子不满足”身高 >= 高个子”的条件）。

public int[][] reconstructQueue(int[][] people) {
    // 按身高降序，身高相同按 k 升序
    Arrays.sort(people, (a, b) -> {
        if (a[0] != b[0]) return b[0] - a[0];  // 身高降序
        return a[1] - b[1];                      // k 升序
    });
 
    // 使用 LinkedList 支持高效的中间插入，O(n) per insert
    List<int[]> queue = new LinkedList<>();
 
    for (int[] p : people) {
        // 将人插入到下标 p[1] 处
        queue.add(p[1], p);
    }
 
    return queue.toArray(new int[0][]);
}

时间复杂度： $O (n^{2})$ （排序 $O (n lo g n)$ ，链表插入每次 $O (n)$ ，共 $n$ 次插入）。

4.3 手工演示

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

排序后：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

步骤	人	插入位置	队列状态
1	[7,0]	0	7,0
2	[7,1]	1	[[7,0],[7,1]]
3	[6,1]	1	[[7,0],[6,1],[7,1]]
4	[5,0]	0	[[5,0],[7,0],[6,1],[7,1]]
5	[5,2]	2	[[5,0],[7,0],[5,2],[6,1],[7,1]]
6	[4,4]	4	[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

最终结果：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]，与题目预期输出一致。

4.4 正确性验证

验证每个人的 k 值：

人	位置	前面身高 ≥ 自己的人	k 值	正确？
[5,0]	0	无	0	✓
[7,0]	1	无（5 < 7，不算）	0	✓
[5,2]	2	[7,0]（身高7≥5）、[5,0]（身高5≥5）= 2	2	✓
[6,1]	3	[7,0]（身高7≥6）= 1	1	✓
[4,4]	4	[5,0],[7,0],[5,2],[6,1]（身高都≥4）= 4	4	✓
[7,1]	5	[7,0]（身高7≥7）= 1	1	✓

第 5 章四道题的模式归纳

5.1 四种贪心模式

题目	贪心类型	核心思路
LeetCode 122（股票）	峰谷累积	正价差之和 = 所有上涨段的利润和
LeetCode 134（加油站）	环形差分	遇到亏损段就重置起始点，总量判断可行性
LeetCode 860（找零）	模拟优先级	优先保留更稀缺/通用的资源（5 美元）
LeetCode 406（队列）	构造排序	高个子先插入，矮个子插入不影响高个子计数

5.2 如何识别这类贪心题

峰谷累积（122 类型）：

特征：序列上的买卖/收益/代价问题，每段独立
识别：利润/代价可以分解为逐步累加
贪心：每步选正收益，跳过负收益

环形差分（134 类型）：

特征：环形路径，每个节点有正负贡献
识别：问能否/从哪里出发完成一圈
贪心：线性扫描，遇到累积量为负时更新起始点；总量决定可行性

模拟优先级（860 类型）：

特征：有限资源，不同资源”通用性”不同
识别：找零/资源分配，多种方案等价但资源消耗不同
贪心：优先保留通用性高（稀缺性强）的资源

构造排序（406 类型）：

特征：根据相对约束排列/构造序列
识别：每个元素有”在多少其他元素前/后”的约束
贪心：排序决定处理顺序，使后插入元素不影响先插入元素的约束满足

5.3 贪心正确性快速判断

以下三个问题可以帮助快速判断贪心是否正确：

局部贪心选择是否”弱化了”后续选择的机会？若是，贪心可能错误（需要 DP）。
是否存在”交换后不变差”的论证？若存在，贪心正确。
是否存在全局最优与局部最优等价的数学变换？若存在（如 122 的价差分解），直接验证。

第 6 章本文核心结论

LeetCode 122（股票 II）的贪心本质是”价差分解”：利润可以分解为每日价差之和，只要把所有正价差纳入即是最优。这是最容易被面试者忽视的简化。
LeetCode 134（加油站）有两个关键定理：总净油量 >= 0 是有解的充要条件；遇到累积量变负时，之前所有站都不可行，重置到下一站。这两个定理一起构成 $O (n)$ 解法的完整论证。
LeetCode 860（找零）的贪心成立因为资源有”通用性层次”：5 美元比 10 美元用途更广，等价方案中优先保留稀缺资源。
LeetCode 406（队列重建）是”构造类贪心”的典型：高身高者先确定位置，低身高者插入不影响高身高者的 k 值约束。这类贪心的关键是找到正确的”处理顺序”，使后续操作不破坏已有约束。
这四道题覆盖了贪心的四种常见子模式：峰谷累积、环形差分、模拟优先级、构造排序。掌握这四种模式，可以应对大多数中等难度的贪心面试题。

汀的知识碎片

文章导航

09 股票与序列贪心：多次交易、加油站与柠檬水找零

股票与序列贪心：多次交易、加油站与柠檬水找零

摘要

第 1 章 LeetCode 122：买卖股票的最佳时机 II

1.1 题目

1.2 峰谷策略的直觉

1.3 贪心实现

1.4 正确性证明

第 2 章 LeetCode 134：加油站

2.1 题目

2.2 核心定理

2.3 贪心：线性找起始点

2.4 手工演示

第 3 章 LeetCode 860：柠檬水找零

3.1 题目

3.2 贪心分析

3.3 柠檬水贪心的适用性

第 4 章 LeetCode 406：根据身高重建队列

4.1 题目

4.2 排序方向设计

4.3 手工演示

4.4 正确性验证

第 5 章四道题的模式归纳

5.1 四种贪心模式

5.2 如何识别这类贪心题

5.3 贪心正确性快速判断

第 6 章本文核心结论

On this page

汀的知识碎片

文章导航

09 股票与序列贪心：多次交易、加油站与柠檬水找零

股票与序列贪心：多次交易、加油站与柠檬水找零

摘要

第 1 章 LeetCode 122：买卖股票的最佳时机 II

1.1 题目

1.2 峰谷策略的直觉

1.3 贪心实现

1.4 正确性证明

第 2 章 LeetCode 134：加油站

2.1 题目

2.2 核心定理

2.3 贪心：线性找起始点

2.4 手工演示

第 3 章 LeetCode 860：柠檬水找零

3.1 题目

3.2 贪心分析

3.3 柠檬水贪心的适用性

第 4 章 LeetCode 406：根据身高重建队列

4.1 题目

4.2 排序方向设计

4.3 手工演示

4.4 正确性验证

第 5 章 四道题的模式归纳

5.1 四种贪心模式

5.2 如何识别这类贪心题

5.3 贪心正确性快速判断

第 6 章 本文核心结论

On this page

第 5 章四道题的模式归纳

第 6 章本文核心结论