贪心
01 / 共享的机制
每一步取局部最优,并能证明这次提交后续不会被推翻。 没有回溯、没有 DP 表:要么用交换论证说明换掉任意一次贪心都不会更优, 要么用领先论证说明贪心在每个前缀上都不落后。 三个经典子模式把这个想法落成算法:对区间排序后取、在数组上扫描追踪可达边界, 以及在累积量上「一旦失败立即重置起点」。
在上面选一个子模式。每个子模式都可以单独跳转 —— 从题目最像的那个开始。
↑ 选一个— / 什么时候用哪个
区间调度
输入是一组区间、问「最多挑出多少个互不重叠」时用。按终点排序后, 每个起点超过已选区间终点的区间就拿。交换论证保证「最早结束」永远安全。
按终点排序 · LC 435 · LC 452
跳跃游戏
每个元素决定你能从这里移动多远时使用。从左到右扫描,维护当前能到达的最远下标; 一旦扫描位置超过这个边界,终点就不可达。
追踪最远 · LC 55 · LC 45
加油站
一段(环形或线性)路径上,某个累积量必须始终非负时用。 一旦运行总和跌破零就把起点重置到下一格 —— 任何使其失败的段都不会是合法起点。
失败即重置 · LC 134 · LC 53