LeetCode · Greedy
完整教程 / Python 3 / OFFLINE EDITION
ALGORITHM NOTEBOOK / 04 LEARNING STAGES

贪心算法
从局部选择，到全局最优。

围绕 5 道经典题，建立“选择是什么、为什么安全、状态如何维护”的完整推理链。先读证明，再写代码，最后用反例检验适用范围。

05经典题目
04学习阶段
10Python 3 解法
∞离线反复复习

Python 3 · 内置语法高亮 · 可逐步推演 · 本机保存学习进度

先看路线，再开始刷题

建议顺序：121 → 122 → 55 → 45 → 763。121 从最优历史入门，122 学会分解收益，55 建立覆盖边界，45 进阶到最少次数，763 练习最早合法切分。这里“进阶”指推理深度，五题最高难度均为中等。

阶段题目与核心状态学会什么
01 · 基础知识与状态压缩固定一个决策，只保留最优历史121 从枚举买卖对出发，理解前缀最小值为什么能支配其他历史选择。
02 · 核心模板与局部收益把总目标拆成可独立实现的收益122 用正差分解证明贪心；与一次交易的 DP 转移对照，识别适用条件。
03 · 典型应用与覆盖边界先判可达，再求最少步数55 维护连续可达前缀，45 把该前缀升级为隐式 BFS 的分层边界。
04 · 进阶推理与区间闭包在最早合法位置做不可撤销决策763 从字符约束推导最早合法切点，再用区间合并建立第二种理解。

每题按 题意 → 观察 → 证明 → 完整代码 → 逐行解释 → 示例 → 复杂度 → 易错点 阅读。所有代码块都是可单独提交的 Solution；不要把同题两种解法拼在一起。O(n) 中 n 表示输入长度，辅助空间默认不包含输入和返回结果，涉及固定字母表时单独注明。

基础知识：什么样的选择可以贪心？

贪心算法在每一步固定一个局部选择，并且不再回头修改。难点通常不是写循环，而是证明：做出这个选择后，仍然存在一个全局最优解与它兼容。

安全选择 + 状态不变量 + 完整遍历 → 全局最优

从四个问题推导算法

  1. 目标：是利润最大、可达性、次数最少，还是分段数最多？先确定优化方向。
  2. 选择：固定卖出日、保留正差、扩大覆盖，还是在合法边界切分？把选择说成具体动作。
  3. 理由：用支配关系、上下界、交换论证或分层最短路解释，不能只说“看起来最好”。
  4. 状态：哪些历史信息足以决定未来？写出循环前后变量的精确定义与失败条件。

贪心、动态规划、暴力枚举如何取舍

方法保留的选择适用判断本册例子
暴力枚举枚举所有候选组合或路径先用于建立小输入基线；注意组合爆炸121 枚举买卖对需 O(n²)
动态规划每个状态保留最优子解多个未来相关状态都不能丢；先明确状态转移122 的 cash / hold；45 的 dp[i]
贪心压缩为已证明安全的决策或边界存在支配关系、可达上界或最早合法切点前缀最低价、全部正差、最远覆盖、最后位置
反例比口号更可靠。“每次跳最远”在 [2,3,0,1,4] 上失败；“只要有正差就累加”在只能交易一次时失败。贪心需要证明具体规则，不能把题目标签当作证明。

四种证明工具

工具核心问题落在代码中
支配关系同一卖出日下，较高买入价有什么优势？没有。121 只保留 min_price
上界与构造任意方案都不超某上界，是否存在方案恰好达到？122 全部正差是上界，逐上涨段交易能达到
不变量与分层维护的范围是否完整？增加一次操作能覆盖哪里？55 连续可达前缀；45 按跳数扩展边界
最早合法切分 / 交换更早为什么不行？此时切分会不会损失未来？763 未完成的字符强制延伸，闭合后立即切分

先修 Python：理解 enumerate、range 的右端不包含、列表与字典、max/min，以及闭区间长度 end−start+1。不需要排序所有题目的输入；本册仅 763 的第二解法对字符区间排序。

STAGE 01
基础知识与状态压缩

121 从枚举买卖对出发，理解前缀最小值为什么能支配其他历史选择。

01LeetCode 121买卖股票的最佳时机

LeetCode 原题 ↗

难度：简单 ｜ 核心知识点：前缀最小值 · 枚举卖出日 · 一次交易

题意与接口

给定每天的股价，按时间顺序完成至多一次买入和一次卖出；买入必须早于卖出。返回最大利润，不交易时利润为 0。

输入约束：1 ≤ n ≤ 10⁵，0 ≤ prices[i] ≤ 10⁴。输入非空；单个价格无法完成交易。

关键观察：固定今天为卖出日，最合适的买入日一定是今天之前价格最低的那一天。只保留最低买入价，就足以压缩所有历史买入选择。

7day 01day 15day 23day 36day 44day 5buy 1 → sell 6 = +5
固定卖出日，用左侧最低价格作为买入候选。绿线表示最优的一次交易。

解法一：前缀最小值（推荐）

解题思路

逐日枚举卖出价格。先用历史最低价计算今天的利润，再把今天价格加入历史最低价。这样计算利润时买入日严格在卖出日之前。best 初始为 0，自动表示可以不交易。

正确性证明 / 不变量

固定卖出日 i，任何更贵的历史买入日都不可能优于历史最低价；用最低价替换买入日不会破坏时间顺序，也不会降低利润。每个合法卖出日都被枚举，所以所有候选利润的最大值就是全局最优。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 1
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = prices[0]
        best = 0
        for i in range(1, len(prices)):
            price = prices[i]
            best = max(best, price - min_price)
            min_price = min(min_price, price)
        return best
关键代码解释
  • min_price = prices[0]：第 0 天只作为初始买入候选，尚未产生利润。
  • best = max(best, price - min_price)：更新前 min_price 只来自 [0, i-1]，保证不能先卖后买。
  • min_price = min(min_price, price)：为下一天保留更便宜的买入选择；best 仍保留过去已找到的最优利润。
时间复杂度O(n)：每个价格至多访问一次。
空间复杂度O(1)：只保存价格、下标和两个标量，不切片。

解法二：动态规划，两个状态压缩

解题思路

cash 表示当天结束时不持股的最大利润，hold 表示当天结束时持股的最大净收益。一次交易下，买入之前的资金只能是 0，因此 hold 只能由 -price 更新。使用旧 hold 更新 cash，清楚体现前一天持有、今天卖出的顺序。

正确性证明 / 不变量

当天不持股只有两条路径：昨天也不持股，或昨天持股今天卖出；当天持股也只有保持或从零资金买入。逐一取最大值覆盖所有合法决策；禁止用历史 cash 再买入，正是“至多一次”的约束。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 2
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cash = 0
        hold = -prices[0]
        for i in range(1, len(prices)):
            price = prices[i]
            old_hold = hold
            cash = max(cash, old_hold + price)
            hold = max(old_hold, -price)
        return cash
关键代码解释
  • hold = -prices[0]：持有一股意味着已经付出价格，净收益可以为负。
  • hold = max(old_hold, -price)：不能写成 cash - price，否则会允许用已获利润开始第二次交易。
  • return cash：最终收益必须处于不持股状态；浮动持仓不等于已实现利润。
时间复杂度O(n)：扫描一次价格序列。
空间复杂度O(1)：使用滚动状态，不需要 n × 2 数组。

解法比较

两种解法均为 O(n) 时间、O(1) 额外空间。前缀最小值最直观，适合面试首选；状态 DP 帮助理解交易次数约束，并能与第 122 题比较。

示例推演

prices = [7,1,5,3,6,4] → 5。选择第 2 天买入、第 5 天卖出；代码下标分别是 1 和 4。

全表预览 · 6 步

点击“下一步”高亮本步状态；完整推演表始终保留，离线与打印都可阅读。

天 i / 价格此前最低价当天利润候选best更新后最低价
0 / 7—不卖出07
1 / 17−601
2 / 51441
3 / 31241
4 / 61551
5 / 41351

DP 对同一输入的 (cash, hold) 依次为 (0,−7)、(0,−1)、(4,−1)、(4,−1)、(5,−1)、(5,−1)，最终同样返回 5。

边界核对

输入预期输出核对点
[5]0一天不能完成买卖
[7,6,4,3,1]0不交易
[2,2,2]0相同价格无利润
[0,4]4股价允许为 0
[1,2,3,4,5]4最早买、最晚卖

易错点

  • 不能先找全局最小值、再找全局最大值相减：[7,1] 中最高价出现在最低价之前，正确答案是 0。
  • 不能累加所有正差：[1,3,2,4] 的一次交易最优为 3，累加得到 4 会违反交易次数限制。
  • min_price 和 best 承担不同职责：前者服务未来，后者记录已经看过的最优结果。
  • 避免 prices[1:] 切片；它会额外分配 O(n) 空间，使 O(1) 空间声明失真。

面试表达：固定卖出日后，历史最低买价支配所有其他买入选择；我用两个标量在一次扫描中维护最优利润。

STAGE 02
核心模板与局部收益

122 用正差分解证明贪心；与一次交易的 DP 转移对照，识别适用条件。

02LeetCode 122买卖股票的最佳时机 II

LeetCode 原题 ↗

难度：中等 ｜ 核心知识点：正差累加 · 收益分解 · 股票状态 DP

题意与接口

每天都可以交易，交易次数不限，但任何时刻最多持有一股；允许同一天先卖再买。返回最大总利润。这里没有手续费、冷冻期或交易次数上限。

输入约束：1 ≤ n ≤ 3 × 10⁴，0 ≤ prices[i] ≤ 10⁴。允许不交易。

关键观察：一段上涨区间的总利润等于它内部相邻正差之和；下跌的差值可以完全跳过。无限次交易使这些正收益能够全部被一套合法交易实现。

7day 01day 15day 23day 36day 44day 5+4+3
只收集两段上涨：1→5、3→6。连续上涨可以合并持有，下降区间不计收益。

解法一：收集每一段正差（推荐）

解题思路

依次计算今天减昨天的股价差。差值为正就累加，差值为零或负就忽略。这里的累加既可以理解为每天在上涨前买入、上涨后卖出，也可以合并成一笔从波谷到波峰的交易。

正确性证明 / 不变量

任意一笔从 b 到 s 的交易利润都能写为相邻差的望远镜和。任意合法交易方案的利润不会超过“全部正差之和”；另一方面，在每个连续上涨段的谷底买入、峰顶卖出，恰好实现全部正差且最多持有一股。上界可以达到，因此最优。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 1
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            diff = prices[i] - prices[i - 1]
            if diff > 0:
                profit += diff
        return profit
关键代码解释
  • range(1, len(prices))：从第二天开始才有相邻差，单元素输入循环为空。
  • if diff > 0：保留可独立实现的正收益；零差累不累加都不影响答案。
  • profit += diff：连续上涨时逐日收益可以相加，不代表同时持有多股。
时间复杂度O(n)：处理 n−1 个相邻差。
空间复杂度O(1)：只有总利润、差值和循环下标。

解法二：持股／不持股动态规划

解题思路

cash、hold 仍分别表示当天结束时不持股和持股的最大净收益。现在允许在卖出之后再次买入，所以买入资金可以来自前一天 cash。用 old_cash、old_hold 明确同时转移。

正确性证明 / 不变量

枚举最后一天的操作：不持股来自保持或卖出，持股来自保持或买入。两类状态涵盖所有合法方案；每个状态只保留收益最高的方案，不会影响未来可选操作。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 2
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cash = 0
        hold = -prices[0]
        for i in range(1, len(prices)):
            price = prices[i]
            old_cash, old_hold = cash, hold
            cash = max(old_cash, old_hold + price)
            hold = max(old_hold, old_cash - price)
        return cash
关键代码解释
  • old_cash, old_hold = cash, hold：把两条转移统一建立在前一天状态上，避免更新顺序引起理解混乱。
  • old_cash - price：允许使用此前交易所得资金再次买入，这是与第 121 题的核心差别。
  • return cash：最后持股不是收益目标，返回不持股的最大利润。
时间复杂度O(n)：每一天进行常数次转移。
空间复杂度O(1)：四个滚动标量。

解法比较

纯正差贪心最短、最便于证明。DP 代码稍长，但更容易迁移到手续费、冷冻期等条件；一旦交易之间存在额外约束，不能直接套用本题的正差结论。

示例推演

prices = [7,1,5,3,6,4] → 7。两笔交易利润分别为 4 和 3；同一输入在第 121 题中只能得到 5。

全表预览 · 5 步

点击“下一步”高亮本步状态；完整推演表始终保留，离线与打印都可阅读。

价格变化相邻差本次计入累计利润
7 → 1−600
1 → 5+444
5 → 3−204
3 → 6+337
6 → 4−207

DP 状态 (cash, hold) 依次为 (0,−7)、(0,−1)、(4,−1)、(4,1)、(7,1)、(7,3)。hold 为正并不表示免费拿到股票，而是此前已实现利润超过当前买入成本。

边界核对

输入预期输出核对点
[5]0没有相邻差
[1,2,3,4,5]4连续上涨合并
[7,6,4,3,1]0连续下跌
[2,2,2]0零差
[1,3,2,4]4两笔交易优于单笔

易错点

  • 不能用全局最大值减全局最小值代替多笔交易利润。
  • 连续上涨 [1,2,3] 的两段收益是 (2−1)+(3−2)=2；可以合并成 1 买 3 卖，没有重复利润。
  • 本题限制最多持有一股；算法没有允许无限买入，也不进行做空。
  • 若有手续费，微小正差可能不值得交易；若有冷冻期，局部正收益不再彼此独立。

面试表达：每笔交易可分解为相邻差，所以所有正差之和是上界；逐段波谷买、波峰卖恰好达到这个上界。

STAGE 03
典型应用与覆盖边界

55 维护连续可达前缀，45 把该前缀升级为隐式 BFS 的分层边界。

03LeetCode 55跳跃游戏

LeetCode 原题 ↗

难度：中等 ｜ 核心知识点：可达前缀 · 最远覆盖 · 反向目标

题意与接口

从下标 0 出发，nums[i] 是在位置 i 能向右跳的最大步数，可以选择更短的步数。判断是否可以到达最后一个下标，返回 Python 的 True 或 False。

输入约束：1 ≤ n ≤ 10⁴，0 ≤ nums[i] ≤ 10⁵。单元素数组已经在终点。

关键观察：不必选择一条具体路径。只要知道当前可达位置构成的连续前缀 [0, farthest]，就能合并所有可行选择。前提是只有可达的点才可以扩展边界。

2index 03index 11index 21index 34index 41 jump1 jumpi=0: reachable [0,2]i=1: reachable [0,4]
路径可以先短跳到 1 再到 4。下方是覆盖边界的扩展，覆盖终点即判定成功。

解法一：向前维护最远覆盖（推荐）

解题思路

farthest 初始为 0。遍历到 i 时，先检查 i 是否超过最远可达边界；若超过，后面的点也无法接入可达前缀，立即失败。否则用 i + nums[i] 扩大覆盖；一旦边界覆盖终点就成功。

正确性证明 / 不变量

初始只有位置 0 可达。假设已处理位置形成连续可达前缀，那么对其中任意 i，可选择 0 到 nums[i] 的任意合法跳长，故加入的覆盖仍与前缀相连。取所有可达 i 的最远端点即得到新的完整可达前缀。若遇到 i > farthest，前缀出现无法跨越的断点，任何后续位置都无从到达。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 1
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        for i, step in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + step)
            if farthest >= len(nums) - 1:
                return True
        return False
关键代码解释
  • if i > farthest：必须先检查可达性，再读取当前位置来扩展边界；否则不可达点也会“贡献”跳长。
  • max(farthest, i + step)：远端不会因一个小步长而缩短；nums[i] 是步长，i + nums[i] 才是绝对下标。
  • farthest >= len(nums) - 1：覆盖终点即可；步数是上限，所以越过终点的能力也能选择落在终点。
时间复杂度O(n)：最坏扫描整个数组，可提前退出。
空间复杂度O(1)：只保留最远下标等标量。

解法二：反向移动目标点

解题思路

goal 初始为终点。从右向左扫描，如果位置 i 能一步到达当前 goal，就把目标收缩到 i。最终 goal 为 0，表示起点可以经由一条链到达原终点。

正确性证明 / 不变量

不变量：当前 goal 一定能够到达终点。若 i + nums[i] ≥ goal，因为允许选更短步数，i 可以先落到 goal，所以新目标仍能到达终点。反之，若从 i 能到终点，某次跳跃必然连接到右侧一个能到终点的位置；扫描全部位置会发现这样的连接，因而不会遗漏可行路径。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 2
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return goal == 0
关键代码解释
  • goal = len(nums) - 1：终点本身可以到达终点，这是反向推理的基点。
  • i + nums[i] >= goal：不必恰好等于 goal，可从允许范围中选恰当步长。
  • return goal == 0：单元素数组循环为空，goal 已为 0，正确返回 True。
时间复杂度O(n)：从右向左扫描 n−1 次。
空间复杂度O(1)：只保存目标下标。

解法比较

两个方向均为 O(n) 时间、O(1) 空间。前向覆盖能自然衔接第 45 题的分层边界；反向目标更简洁，适合检验自己是否理解“可到达”关系。

示例推演

nums = [2,3,1,1,4] → True。可选路径 0 → 1 → 4；前向代码在 i = 1 时已经得到结论。

全表预览 · 2 步

点击“下一步”高亮本步状态；完整推演表始终保留，离线与打印都可阅读。

下标 inums[i]旧 farthest检查后新 farthest结论
0202可达范围 [0,2]
1324覆盖终点，返回 True

失败例 [3,2,1,0,4]：i=0、1、2、3 更新后的 farthest 始终为 3；i=4 时先检测到 4>3，返回 False。反向算法在成功例中的 goal 变化为 4→3→2→1→0。

边界核对

输入预期输出核对点
[0]True起点就是终点
[0,1]False起点无法前进
[2,0,0]True跨过中间零
[1,0,1]False可达边界停在 1
[2,3,0,1,4]True必须允许选择短跳

易错点

  • “每次跳得最远”不是本题贪心：[2,3,0,1,4] 从 0 跳满到 2 会卡住，但走 0→1→4 可达。
  • 有 0 不代表失败：[2,0,0] 能直接抵达终点；关键是整个可达边界能否越过阻塞。
  • 不能先更新 farthest 再判断 i 是否可达；[0,2,3] 的后两个位置不能贡献任何能力。
  • 终点下标是 n−1；[0] 应返回 True，不需要进行一次跳跃。

面试表达：我的贪心状态是所有可行路径的最远覆盖边界，不是当前站在哪个点；只有可达点才能扩大这个边界。

04LeetCode 45跳跃游戏 II

LeetCode 原题 ↗

难度：中等 ｜ 核心知识点：隐式 BFS · 分层贪心 · 最少跳数

题意与接口

与第 55 题相同的跳跃规则，求到达最后一个下标的最少跳跃次数。原题保证终点可达；这里的可提交解法依赖这个前提。

输入约束：1 ≤ n ≤ 10⁴，0 ≤ nums[i] ≤ 1000，保证终点可达。n=1 时答案为 0。

关键观察：按跳跃次数分层：end 是当前 jumps 次跳跃覆盖的右边界，farthest 收集这一层所有位置再跳一次的最远端点。扫描完一层才承诺增加一次跳跃。

2index 03index 11index 21index 34index 41 jump1 jump0 jumps1 jump: [1,2]2 jumps: [3,4]
下方按“最少跳数”分层：起点为第 0 层，[1,2] 为第 1 层，[3,4] 为第 2 层。上方是一条最短路径。

解法一：区间分层贪心（推荐）

解题思路

扫描到倒数第二个位置即可。每个 i 先扩展 farthest；到达当前层的 end 时，说明当前跳数的候选起跳点已全部处理，于是 jumps 加一，把 end 推进到 farthest。这是在数组上压缩了 BFS 队列，不需要逐条枚举边。

正确性证明 / 不变量

设 Rₖ 是用至多 k 次跳跃能覆盖的最远下标，R₀=0。则 Rₖ₊₁=max(i+nums[i])，其中 0≤i≤Rₖ。连续覆盖性质保证每层的可达范围没有空洞。算法在扫描到 Rₖ 时正好完成这一最大值计算；第一次使边界覆盖终点的层数就是最小跳数，因为更少层尚未覆盖终点。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 1
from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        end = 0
        farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:
                jumps += 1
                end = farthest
        return jumps
关键代码解释
  • range(len(nums) - 1)：不处理终点的起跳决策，否则到终点后可能再多计一次；单元素输入自然返回 0。
  • farthest = max(...) 在判断前：先把当前边界位置的跳跃能力也纳入下一层，然后才能结算。
  • if i == end：这是“扫描完当前层”，不是说实际路径必须落在 end。
  • end = farthest：下一层边界来自这一层所有候选点的共同最大覆盖，无须选择具体落点。
时间复杂度O(n)：每个下标只处理一次，隐式边不展开。
空间复杂度O(1)：三个状态变量；不存路径或 BFS 队列。

解法二：动态规划（建立基线）

解题思路

dp[i] 表示到达下标 i 的最少跳数。对每个 i 枚举所有前驱 j<i，若 j+nums[j]≥i，就尝试 dp[j]+1。用这个完整但较慢的解法帮助推导最短路结构，也适合小输入对拍。

正确性证明 / 不变量

任何到达 i 的路径都有一个最后起跳点 j<i。枚举所有能覆盖 i 的 j 并取最小值，就覆盖所有可能的最后一步。dp[0]=0；按下标递增计算，所有前驱已经求得，归纳可知每个 dp[i] 均最优。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 2
from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [n] * n
        dp[0] = 0
        for i in range(1, n):
            for j in range(i):
                if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]
关键代码解释
  • dp = [n] * n：可达时最短路至多 n−1 次，所以 n 是安全的不可达哨兵。
  • j + nums[j] >= i：判断前驱能否一步覆盖当前点，不能只检查相邻位置。
  • dp[j] + 1：加的是一次跳跃，不是 nums[j] 的步长。
时间复杂度O(n²)：枚举全部 j<i，原题规模下 Python 可能超时，仅作教学基线。
空间复杂度O(n)：保存每个下标的最少跳数。

解法比较

面试与提交优先分层贪心 O(n)/O(1)。DP 的优势是状态直接、方便验证，但 O(n²) 对 n=10⁴ 不适合实际提交性能要求。这里展示的 DP 符合接口与逻辑要求，不承诺在最大规模通过时限。

示例推演

nums = [2,3,1,1,4] → 2。最短路径可为 0 → 1 → 4；end 的变化 0→2→4 并不是实际落点路径 0→2→4。

全表预览 · 4 步

点击“下一步”高亮本步状态；完整推演表始终保留，离线与打印都可阅读。

i / nums[i]扩展后 farthest结算前 end是否换层jumps / 新 end
0 / 220是1 / 2
1 / 342否1 / 2
2 / 142是2 / 4
3 / 144否2 / 4

同一示例的 DP 数组为 [0,1,1,2,2]。对 i=4，可用的前驱包括 j=1（dp[1]+1=2）和 j=3（dp[3]+1=3），取最小值得 2。另一个原题示例 [2,3,0,1,4] 也返回 2。

边界核对

输入预期输出核对点
[0]0已经到达终点
[1,0]1只需一跳
[1,1,1,1]3每跳前进 1
[5,0,0]1一跳覆盖终点
[2,3,0,1,4]2不能贪心固定最远落点

易错点

  • 不能把 nums[i] 的值当成跳跃次数；一跳可以跨多个下标。
  • 不能每次固定落到最远的位置：[2,3,0,1,4] 会因此困在 2。
  • end 与 farthest 不能混用：前者固定当前层边界，后者累计下一层覆盖。
  • 原题保证可达。若迁移到不保证可达的版本，需要先用第 55 题判断，或在层结算时发现 farthest==end 且尚未到终点则返回 -1。不要把本代码用于不可达输入并期待 -1。

面试表达：我把 BFS 的每一层压缩成覆盖区间，扫描完当前层才增加一次跳跃；第一次覆盖终点的层数就是最小跳数。

STAGE 04
进阶推理与区间闭包

763 从字符约束推导最早合法切点，再用区间合并建立第二种理解。

05LeetCode 763划分字母区间

LeetCode 原题 ↗

难度：中等 ｜ 核心知识点：最后出现位置 · 区间闭包 · 最早合法切分

题意与接口

把字符串按原顺序切成尽可能多的连续片段，使同一种字母只能出现在一个片段中。返回各片段长度，片段拼接后必须恰好还原原字符串。

输入约束：1 ≤ n ≤ 500，字符只含小写英文字母，因此不同字符数 σ≤26。

关键观察：当前片段只要包含一个字符 c，就必须覆盖到 c 的最后一次出现位置。遇到新字符可能继续拉长边界；扫描位置等于所有已见字符的最远最后位置时，才首次允许切分。

ababcbaca[0,8] → 9defegde[9,15] → 7hijhklij[16,23] → 8
三个片段的字母集合互不重叠；虚线处为最早合法切点，长度之和 9+7+8=24。

解法一：最后出现位置 + 贪心扫描（推荐）

解题思路

第一遍建立 last[c]。第二遍从左向右，把 end 更新为当前片段已见字母的最后位置最大值。当 i==end，当前片段里的所有字母都不会在未来出现，立即切分，并让下一个片段从 i+1 开始。

正确性证明 / 不变量

扫描到 i<end 时，已有字符还会在 end 出现，提前切分一定违法；i==end 时，片段里所有字符的最后出现位置都不超过 i，切分必然合法。这是最早合法切点。任何合法方案的第一段都不能更早结束；把它改为此处结束，原第一段剩余部分仍可与后续合法分段共存，因此片段数不会减少。对剩余后缀重复，得到最多片段。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 1
from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {ch: i for i, ch in enumerate(s)}
        start = 0
        end = 0
        lengths = []
        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                lengths.append(end - start + 1)
                start = i + 1
        return lengths
关键代码解释
  • last = {ch: i ...}：相同键会被后出现的下标覆盖，字典最终留下最后位置。
  • end = max(end, last[ch])：只允许扩大边界；直接写 end=last[ch] 会丢掉更早字符的未完成约束。
  • end - start + 1：使用闭区间 [start,end]，长度必须加 1。
  • start = i + 1：新片段从切点下一位开始；end 无须重置，因为下一字符的 last 至少为其当前下标。
时间复杂度O(n)：预处理与扫描各一次，哈希访问按均摊 O(1) 计。
空间复杂度O(σ)，σ≤26，原题可视为 O(1) 额外空间；返回列表 O(k)，k 为片段数，不计入辅助空间。

解法二：字符首尾区间合并

解题思路

为每个字符记录从首次到最后一次出现的闭区间。任意互相重叠的字符区间必须属于同一个片段。把这些区间按左端点排序，合并重叠部分，不重叠时输出前段长度。

正确性证明 / 不变量

一个字符的首尾位置必须在同一片段，其间字符也必须被纳入；重叠区间不能分居两个不相交片段，所以必须合并。合并后相邻区间不重叠，边界两边没有共享字符，故可以切分；继续合并不同连通块只会减少段数，所以每个合并块单独成段最优。

完整 Python 3 代码
Python 3 · 独立提交 · 解法 2
from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        first, last = {}, {}
        for i, ch in enumerate(s):
            if ch not in first:
                first[ch] = i
            last[ch] = i
        intervals = sorted((first[ch], last[ch]) for ch in first)
        left, right = intervals[0]
        lengths = []
        for a, b in intervals[1:]:
            if a <= right:
                right = max(right, b)
            else:
                lengths.append(right - left + 1)
                left, right = a, b
        lengths.append(right - left + 1)
        return lengths
关键代码解释
  • sorted((first[ch], last[ch]) ...)：按左端点排序，把字符约束显式转成区间问题。
  • if a <= right：仅合并有重叠的闭区间；[0,2] 和 [3,4] 可以分开，不能误用 a<=right+1。
  • lengths.append(...) 在循环后：最后一个合并块没有后继触发输出，必须手动收尾。
时间复杂度O(n + σ log σ)：建表 O(n)、排序 O(σ log σ)、合并 O(σ)；σ≤26 时总体为 O(n)。
空间复杂度O(σ) 额外空间，包括字典、区间、排序及切片；另有 O(k) 返回结果。原题固定字母表下辅助空间为 O(1)。

解法比较

最后位置扫描无需排序，更简洁，优先掌握。区间合并帮助理解“互相牵连的字符必须整段保留”；在字母表可变时，它比线性扫描多一个 σ log σ 排序项。

示例推演

s = "ababcbacadefegdehijhklij" → [9,7,8]，对应 "ababcbaca" | "defegde" | "hijhklij"。

全表预览 · 12 步

点击“下一步”高亮本步状态；完整推演表始终保留，离线与打印都可阅读。

扫描位置 / 字符last[字符]更新后 end动作
0 / a88开启第一段
1 / b58保留更远约束
2…7 / a,b,c,b,a,c8,5,7,5,8,78继续扫描
8 / a88切分 [0,8]，长 9
9 / d1414开启第二段
10 / e1515扩到 15
11…14 / f,e,g,d11,15,13,1415尚不能切分
15 / e1515切分 [9,15]，长 7
16 / h1919开启第三段
17…18 / i,j22,2323扩到 23
19…22 / h,k,l,i19,20,21,2223继续扫描
23 / j2323切分 [16,23]，长 8

区间法中，a:[0,8]、b:[1,5]、c:[4,7] 合并为 [0,8]；d/e/f/g 合并为 [9,15]；h/i/j/k/l 合并为 [16,23]。另一个原题示例 "eccbbbbdec" → [10]。

边界核对

输入预期输出核对点
"a"[1]单字符
"aaaa"[4]同字符不可分开
"abc"[1,1,1]每个字符独立
"eccbbbbdec"[10]约束交叠成整段
"abacb"[5]边界必须取 max

易错点

  • 目标是片段数量最多，不是让第一个片段尽量长；一旦合法就应立刻切分。
  • 只看当前字符下一次出现不够，必须知道最后出现位置；片段中其他字符也可能继续延伸边界。
  • 不要用 end=last[ch] 代替 max；例如 "abacb" 的合法答案为 [5]，中途缩小边界会错误切分。
  • 空间分析要注明字母表与返回列表：原题 σ≤26；若推广到任意字符，字典空间是 O(σ)，不应无条件写 O(1)。

面试表达：每个字符的最后出现位置给出片段的强制右边界；我持续取最大值，在扫描位置首次追上边界时立即切分。

核心模板：把变量含义一起记住

下表是已在各题完整代码中实现的核心更新。它们不是能直接混用的通用算法；复制上方对应题目的完整解法再提交。

模板 / 代表题状态含义关键更新适用前提
前缀最优 / 121min_price 是当前卖出日之前的最低价best = max(best, price - min_price)至多一次交易，先计算利润再更新最低价
独立收益 / 122profit 是已扫描相邻正差之和profit += max(0, diff)不限次数，无手续费与冷冻期
连续覆盖 / 55farthest 是可达前缀右端farthest = max(farthest, i + step)先保证 i 可达；允许选择不超过上限的任意跳长
分层覆盖 / 45end 固定本层边界；farthest 累计下一层if i == end: jumps += 1; end = farthest终点可达；扫描到 n−2，先扩展再换层
约束闭包 / 763end 是本段已见字符最后位置的最大值end = max(end, last[ch])只有 i==end 时切分；目标是最多片段

两组最容易混淆的条件

比较前者后者不要混用
121 与 122一次交易：hold=max(hold,−price)不限次数：hold=max(hold,old_cash−price)正差累加只适用于 122 的条件
55 与 45只回答能否到达：一个覆盖边界最少跳数：当前层与下一层两个边界可达不等于最短；也不是挑某个最远落点
55 与 763覆盖越远，未来可选位置越多边界必须覆盖当前片段全部字符约束763 在最早合法位置切分，不能一味拉长首段

复杂度速查

题号推荐解法时间辅助空间第二解法时间 / 辅助空间
121O(n)O(1)状态 DP：O(n) / O(1)
122O(n)O(1)状态 DP：O(n) / O(1)
55O(n)O(1)反向目标：O(n) / O(1)
45O(n)O(1)DP：O(n²) / O(n)，大输入可能超时
763O(n)O(σ)，原题 σ≤26区间合并：O(n+σ log σ) / O(σ)

763 的返回列表另占 O(k)，原题 k≤26；若推广到任意字符，k 可以随 n 增长。第 45 题的路径重建需要额外保存前驱，本册只返回题目要求的最少跳数。

面试自测与反例清单

“已掌握”建议满足三个条件：能闭卷写出推荐解法；能解释不变量和证明；能主动说出一个容易误用的条件。下面的自测勾选独立于题目掌握进度，也会自动保存。

错误主张最小化思考用例正确结论
所有股票题都累加正差121: [1,3,2,4]一次交易利润 3，多次交易才是 4
数组有零就无法到终点55: [2,0,0]可直接跳到终点，True
只要索引还在数组中就可以扩展55: [0,2,3]下标 1 不可达，False
最少次数等于不断落到最远点45: [2,3,0,1,4]走 0→1→4，2 次
字符最后位置可以覆盖旧边界763: "abacb"必须取 max，整段长度 5
闭卷练习：用 60 秒讲清一道题
  1. 用自己的话说目标与限制，特别是交易次数和可达保证。
  2. 先给一个可行的基线，再指出哪些信息可以压缩。
  3. 定义状态，说明每轮循环前后的含义。
  4. 用反例排除一个错误贪心，再证明你的选择安全。
  5. 走一个示例，最后报告时间、辅助空间、返回空间和边界。

五天学习计划与复习节奏

时间内容建议用时验收动作
Day 1 · 阶段一基础知识 + 121 两解45–60 分钟从 O(n²) 枚举推导最低买价；解释更新顺序
Day 2 · 阶段二122 两解；对比 12145–60 分钟证明正差上界可达到；说出何时不能套用
Day 3 · 阶段三上55 前向与反向45–60 分钟跟踪成功与失败样例；解释连续覆盖
Day 4 · 阶段三下45 分层贪心与 DP60–75 分钟画出 R₀、R₁、R₂；解释不遍历终点
Day 5 · 阶段四763 两解 + 五题闭卷75–90 分钟证明最早切分；五题均能给出边界与复杂度

间隔复习：学后第 1 天口述证明，第 3 天闭卷重写，第 7 天混合重做五题，第 14 天只看题意再选模板。若写错，记录“哪个不变量被破坏”，再取消该题已掌握标记，下一次专门复测。

本册完成标准：能从限制推导选择，从选择推导状态，再用不变量或交换论证解释代码。速度建立在这些判断稳定之后。

离线使用与资料说明

HTML 内已包含全部样式、脚本、SVG 和高亮代码。阅读、搜索、复制、逐步推演、主题切换与进度记录无需联网；“原题”链接用于联网后访问力扣。

进度保存在当前浏览器的 localStorage 中，不会自动跨设备同步。建议长期使用同一浏览器与同一路径；移动文件、使用隐私模式、清理站点数据可能导致原记录不可见。若浏览器禁止本地存储，会显示提示，并继续提供当前页面内的进度标记。

题号、难度、约束与示例输出依据各题力扣中文原题页核对（2026-10-31）；题意采用简述，教学、证明和代码为本册编写。原题参考入口：

121 买卖股票的最佳时机 · 122 买卖股票的最佳时机 II · 55 跳跃游戏 · 45 跳跃游戏 II · 763 划分字母区间