导弹打飞机贪心算法：最少拦截系统与偏序链覆盖详解-北京尧图网络

导弹打飞机问题的贪心算法在很多算法题单里和面试题本里都有它的身影经典叫法包括“最少拦截系统”“拦截导弹”“导弹打飞机”。我第一次碰到这道题时的第一反应是“这不就是个最长下降子序列吗”结果顺着这条思路做出来只对了一半它前半问的确实是单套系统最多能接几个目标但后半问的是最少要开多少套系统真正想考的是贪心以及你有没有意识到这个贪心背后的偏序结构。这篇文章把我后来完整的推导过程、代码、防坑点和扩展方向都整理一遍希望帮你一次把这个模型吃透。1. 先把题目翻译成人话它到底要我们算多少个“拦截链条”很多人看到“导弹打飞机”这种题目描述就容易去脑补复杂的军事建模其实题目只是一个抽象后的序列覆盖问题。我平时刷题总结下来的经验是先把那些战斗化包装全部剥掉只看数据关系否则很容易被题面带到坑里。1.1 题目常见描述与输入输出题面通常长这样有一串目标依次出现每个目标有一个高度值 h。一套拦截系统可以连续拦截多个目标但有一个硬性条件同一套系统下一次拦截的目标高度不能高于上一次拦截的高度。也就是说一套系统覆盖的目标序列必须是一个非递增序列。问两件事第一单套系统最多能拦截多少个目标第二如果要拦截全部目标最少需要准备多少套系统。有些版本会把第一问省略只问第二问。题目的输入就是一个数组比如5 1 4 2 3对应的输出是2为什么是 2一种覆盖方式是第一套系统打 5 4 3第二套系统打 1 2但这不对因为时间顺序是固定的你只能按输入顺序决定是否用当前目标不能把数组重新排序。正确的看法是把这个序列拆成尽可能少的非递增子序列。有些人可能第一反应是“那直接按高度排序不就行了把高的都给第一套低的给第二套”这绝对不行。目标出现的顺序没有换你只能在时间线上做分配。这种“不能重排”的限制是整个题目的第一块敲门砖。1.2 一句话模型非递增链覆盖抛开“导弹”“飞机”“系统”这些名词题目的数学结构特别干净给定一个序列 a[1..n]要求把这个序列划分成尽可能少的子序列使得每个子序列内部保持非递增关系。这里子序列指的是按原顺序选取的元素组合不是连续子段。这个模型在算法里叫链覆盖。每个子序列就是一条链链与链之间互相独立目标就是最小化链条数。理解这个模型之后第二问就变成了“最小链覆盖”问题。如果你熟悉图论会想到一般的最小路径覆盖可以用二分图最大匹配来做但在这个特殊偏序结构里存在一个非常简单的贪心方案这也是题目想重点考察的东西。1.3 这个题和贪心有什么关系“最少需要几套系统”这个问法天然适合贪心目标一个一个来系统一条一条开每次决策只考虑当前目标给谁。问题是怎么决策才最优。贪心的基本思想是“局部最优尽量不损害全局最优”。在这道题里每个目标的高度相当于它对系统能力的需求每个系统的当前尾部高度相当于它剩余的能力。我们要把当前目标塞给某个系统同时还希望未来的目标更好安排。于是核心问题就出现了如果当前有多个系统都能接住这个目标到底要给哪一个选错了会不会让答案变大这是后面两节要解决的内容也是整道题能不能真正掌握的分水岭。2. 贪心策略的推演新目标来了该交给哪一条拦截链先别急着写二分也别急着背模板。我建议你亲手推一遍贪心过程因为面试官问你“为什么这样贪是对的”时大部分人都是卡在这里。2.1 先看一个不靠谱的贪心谁排在前面就给谁最容易想到的做法是维护一个系统列表每个系统记录它上一次拦截的高度。来了新目标就从头扫系统列表找到第一个能接的系统更新它的尾部高度从头到尾找不到能接的就新开一个系统。这个做法在某些数据上能过但它经不起推敲。举个例子目标序列 6 3 5 4按“第一个能接”的规则处理6 来了没有系统开系统 A尾部记为 63 来了系统 A 能接A 尾部变成 35 来了系统 A 尾部 3 接不了 5开系统 B尾部记为 54 来了系统 A 接不了 4系统 B 尾部 5 能接B 尾部变成 4最后用了 2 套系统。这个结果看起来没问题但换个数据就暴露了如果第一个能接的系统尾部高度本来就很高你把它降下来会浪费它原有的“大空间”。比如系统 A 尾部是 100系统 B 尾部是 60新目标高度是 50。两个系统都能接。如果你选 AA 尾部变成 50系统 B 还是 60如果选 BB 尾部变成 50系统 A 还能保持 100。接下来如果来个高度 70 的目标前一种方案已经没有任何系统能接 70 了后一种方案里系统 A 还能接。所以“第一个能接就给谁”只是一个可运行的方案不是一个正确的贪心。2.2 正确规则在能接的链里挑尾部最小正确贪心规则是新目标 x 到来时在所有“当前尾部高度 x”的系统中选择尾部高度最小的那个系统来接如果没有任何系统能接那就新开一个系统。为什么是“尾部最小”而不是“尾部最大”这个容易想反。我们要保留的是系统的剩余拦截能力也就是它当前尾部的高度。尾部越高说明这个系统越有能力接高空目标。所以每当我们必须用一个系统去接低空目标时应该优先消耗那些“刚好能接、能力最接近”的系统把尾部更高的系统留到后面应对高目标。你可以把它理解成手里有几把尺子每把尺子的最大量程就是尾部高度。现在来了一个长度为 x 的物体要用尺子去量能用最小量程的那把就用最小量程的把大量程的尺子留到以后可能出现的更长的物体上。这种贪心和经典的活动安排很像谁越紧迫、谁越不灵活就先处理谁。2.3 为什么不担心“从高往低派”更好很多人会追问能不能反过来把每个目标尽量交给当前尾部最高的系统也就是“能接就往高能力系统上堆”。我试过这个策略将来某些数据会出问题。看一组模拟数据尾部集合是 [4, 8]新目标高度是 3。如果选尾部 4 的系统新尾部集合是 [3, 8]如果选尾部 8 的系统新尾部集合是 [3, 4]第一种方案留下一个 8后面来了高度 5、6、7 的目标都还能接第二种方案留下的最大尾部只有 4后面来高度 5 就必须开新系统了。这说明选择尾部更高的系统看似在做“能力合并”实际上是在把大盘能力砸到小需求上属于资源错配。贪心问题里有一条通用直觉能用小资源解决的问题不要动大资源。当然这里我补充一点上面的 [4, 8] 例子中如果先选 8当前目标 3 虽然消耗了大系统但另一个 4 还在是不是也未必错误单独看这一轮确实不一定会导致系统数变多但构造更长序列时偏差会被放大。贪心证明的核心是用“交换论证”假设最优解里某一步把 x 给了尾部更大的系统 t1而尾部更小的系统 t2 也能接那么把这次分配交换成 t2 接 xt1 保持原状后续所有目标仍然可以按原方案完成分配不会产生新的冲突。所以“选尾部最小可接系统”绝对不会劣于其他选择它才是安全策略。3. 从 O(n²) 暴力到 O(n log n)一份可以直接抄的代码理解了贪心策略实现就顺理成章了。我建议动手前先写一个慢但正确的暴力版本拿它和优化版本对拍这样能快速验证后面的二分思路有没有写歪。3.1 暴力维护“系统尾值表”第一种实现方式很直白用一个数组 tailtail[i] 表示第 i 套系统当前最后拦截的高度。来了新目标 h遍历整个 tail找出所有大于等于 h 的位置挑其中 tail 值最小的那个去更新找不到就 append 一个新系统。def min_systems_slow(seq): tails [] # 每个系统的当前尾部高度 for h in seq: idx -1 best float(inf) for i, t in enumerate(tails): if t h and t best: best t idx i if idx -1: tails.append(h) else: tails[idx] h return len(tails)这段代码的时间复杂度是 O(n*m)m 是系统数量最坏情况下 m 也接近 n所以整体是 O(n²)。优点是逻辑完全贴合贪心规则不会因为二分边界写错而挂掉。刷题调试时它是最好的参照物。3.2 二分位置 lower_bound 的优化逻辑要让整体复杂度降下来关键点是观察按照“挑最小可接系统”的规则tails 数组始终是单调不减的。为什么初始为空天然有序。假设 tails 在更新前是单调不减的一个新目标 h 到来我们用二分找到第一个大于等于 h 的位置 pos也就是 tails[pos] h并且 pos 之前的尾部值都小于 h。更新后tails[pos] h。新值 h 仍然大于 tails[pos-1]并且小于等于原来的 tails[pos1]因为原来的 tails[pos] tails[pos1]而 h 原来的 tails[pos]所以单调性保持。这个单调性是整个世界的地基。有了它就可以用二分查找。在 Python 里可以直接用 bisect 库from bisect import bisect_left def min_systems_fast(seq): tails [] for h in seq: pos bisect_left(tails, h) if pos len(tails): tails.append(h) else: tails[pos] h return len(tails)和暴力版本对比会发现快速版本里没有显式“找最小可接系统”的循环它直接通过 bisect_left 找到了第一个大于等于 h 的位置。由于 tail 有序第一个大于等于 h 的位置正是“尾部值最小且能接住 h”的系统。3.3 完整代码和单链最长拦截数的对照实现实际题目如果同时问两个问题还需要求“单套系统最多能拦截多少个目标”它对应的是最长非递增子序列长度。这个可以用朴素动态规划实现def longest_non_increasing_subseq(seq): n len(seq) dp [1] * n for i in range(n): for j in range(i): if seq[j] seq[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) if n else 0这样一整套题目的答案就是两个值最长非递增子序列长度、最少系统数。我贴一个完整的示例方便你直接自测输入 9 389 207 155 300 299 170 158 65 140 输出 6 # 单套系统最长拦截数 2 # 最少系统数第一问的 6 是指一条最长非递增链可以是 389 300 299 170 158 65长度 6。第二问的 2 指两条链就能覆盖全部一条是 389 300 299 170 158 65另一条是 207 155 140。贪心算出来的答案和手算完全一致。4. 背后那块数学基石为什么答案等于最长严格递增子序列长度如果只背模板你大概率记不住什么时候用 bisect_left什么时候用 bisect_right。这道题最好的记忆方式是直接理解它的数学结构理解一次之后边界条件就再也不会弄混了。4.1 把“能接续”定义成一个偏序关系设两个目标 i 和 j并且 i 在原序列中出现在 j 之前。如果高度 a[i] a[j]那么它们可以在同一套系统里先后被拦截反过来如果 a[i] a[j]它们就不能在同一条链里共存。注意这里的关系是有方向、有先后限制的。我们用“i 可以接在某个元素的后面”来定义一条链。链内任意连续两个元素都满足“后面的高度不大于前面的高度”。这是经典偏序元素之间的继承关系由“位置更晚、高度不增”决定。4.2 Dilworth 定理在这个场景里的直观解释偏序集有一个著名的定理把集合划分成最少的链这个最少链数等于最长反链的长度。反链在这里指一组元素任意两个元素之间都不能出现在同一条拦截链里。翻译成最直白的话就是这些元素两两都“互相冲突”谁也没法接谁。什么时候两个元素冲突位置靠后的那个目标高度反而比位置靠前的高。所以一个反链就是位置从左往右走高度严格递增的一个子序列。于是结论瞬间清晰最少链数最长严格递增子序列长度。可能有些读者觉得定理太抽象没关系我也提供一个低配版解释。看贪心算法的 tails 数组它实际上维护了“当前可构造的每条严格递增子序列的尾部最小可能值”。用二分维护之后tails 的长度永远是已经见过的元素中最长严格递增子序列的长度。这个长度又恰好等于系统数因为每开一个新系统就等价于发现了一个更大的严格递增序列长度。4.3 用几组数据把结论锤结实光说理论不如跑几组数据。下面是我在验证时常用的一组用例可以直接抄去跑输入序列肉眼观察的最小链方案最长严格递增子序列长度最少系统数5 4 3 2 1一条链5 4 3 2 1111 2 3 4 5每条链只有一个元素553 2 4 13 2 1 4228 3 4 5 18 3 1 4 5332 4 1 3 52 1 4 3 533第一行里最长严格递增子序列长度只有 1因为整段高度一直在降所以一套系统就能覆盖。第二行完全反过来高度持续上升任何两个目标都不能放进同一条链只能每个目标一套系统答案等于 n。用这个表你能很直观地感受到系统数不是看有多少个“波峰”或“下降段”而是看最长的“上升挑衅序列”有多强。5. 提交时最容易翻车的三个细节这道题代码量很少真正的难点藏在边界条件里。我在这三个坑上摔过不止一次每次面别人时也最爱问这几个点。5.1 等号处理非递增和严格递减是两套答案原题是“不高于前一次”也就是允许高度相等。比如序列 5 5 5一套系统就能全接。此时对应的是最长严格递增子序列长度因为只有严格上升的元素才算冲突。如果题目改成“必须低于前一次”那就是严格递减要求。等高的两个元素不能放同一条链最少系统数会变成最长非递减子序列长度。体现在二分上是允许相等时用 bisect_left找第一个不小于 h 的位置要求严格递减时用 bisect_right找第一个大于 h 的位置。很多同学直接背“拦截导弹用 lower_bound”结果题目改了“严格”两个字就全错。拿到题第一步一定要确认题目给的是还是。5.2 tail 数组的单调性别被你的维护方式破坏tails 单调不减这个性质必须建立在“每次都在第一个大于等于 h 的位置更新”的基础上。如果你偷懒写成“从头找最小可接系统”并且在选择时没有按照单调位置维护tails 可能变成乱序后面的二分就完全失效。拿暴力对拍时也要注意暴力版本选的应该是所有可接系统里 tail 值最小的那个而不是第一个可接的。第一个可接的方案本身不一定错但它和二分版本不是同一个贪心策略对拍对不上会让你白白浪费时间。5.3 lower_bound 还是 upper_bound一个字母决定对错面试时一道经典追问是“到底该用哪一个”背后的判断逻辑是这样的如果允许接住等于当前高度 h 的目标你要找第一个 h 的位置用 bisect_left如果只能接住大于 h 的目标你要找第一个 h 的位置用 bisect_right推荐一套自查流程先写出链的判定不等式比如“a[i] a[j] 才能接续”然后把不等式取反看看反链是什么。反链是严格递增还是非递减二分就明确了。这个方法比硬记模板可靠遇到变体也不会慌。6. 从拦截链到会议安排这道题的孪生兄弟们很多人刷题喜欢一道一道刷刷完就忘。我更建议做完一道题后把它放到更大的贪心框架里看。导弹打飞机问题并不是孤例。6.1 会议室最少数量问题的同构变换会议室问题长这样给一组会议的起止时间问最少需要多少个会议室。做法是先把会议按开始时间排序然后维护当前正在开会房间的结束时间用一个小根堆。来一个新会议时看最早结束的房间能不能腾出来能腾则复用不能腾就开新房间。这和导弹打飞机高度同构。会议的开始时间是“强制顺序”结束时间对应拦截系统的尾部高度。每开一个新会议室等效于发现了一个无法被任何现有资源覆盖的需求于是资源数量加一。唯一区别是导弹问题因为只维护一个单调数组所以用二分就够会议问题同时涉及多个维度的“最晚利用率”用小根堆更合适。我在面试里会把这两个问题放在一起讲目的是向面试官展示你不只是背题而是能看到不同包装底层的资源调度模型。6.2 加上“每链最多拦截 k 个”之后贪心为什么失效导弹打飞机之所以能贪心是因为每条链没有长度限制链之间的约束只有一个尾部高度。一旦题目改成“每套系统最多拦截 k 个目标”情况就变了你不仅要考虑当前尾部高度还要考虑每条链已经用了多少个名额。选中一个系统既消耗它的高度空间也消耗它的剩余数量。这时简单的尾部最小策略就不一定最优了。比如两条链一条尾部很高但已经用了大量名额另一条尾部稍低但名额充足新目标高度不高不低你选谁需要权衡两个维度贪心很难保证全局最优。这种问题更适合动态规划或网络流建模。这也是为什么我建议刷题时多问一句“这个模型的边界条件改一下贪心还成立吗”这对理解模型本质特别有帮助。6.3 什么时候需要上动态规划或者二分图匹配如果题目不仅要覆盖全部目标还要让每个目标的“延迟”“消耗”“价值”参与优化就不再是最小链覆盖而是带权覆盖问题。比如目标是打掉尽可能多的高分飞机系统数量有限每套系统的拦截次数有限这就变成了带约束的组合优化。常见的通用手段是把每个目标看作一个节点把“能接续”的关系看作边问题变成在 DAG 上求最小路径覆盖或最大匹配。可以用二分图匹配解决复杂度大概是 O(n * sqrt(n)) 级别但编码成本高很多。所以做题前先判断链无长度限制、无权重、全部覆盖这三个条件同时满足时贪心才是首选方案。7. 我实际刷题时的思考顺序收尾最后分享一套我自己总结的思考流程不一定适合所有人但希望能帮你减少在类似题上走弯路。拿到题先不要急着写二分。先把题目改写成纯数据模型目标序列是什么接续关系是什么链长有没有限制是否存在权重。以上四点只要有一个被题目的额外条件包住就要警惕贪心是否仍然成立。第二步是先写暴力。暴力代码不丢人它是最快的验证工具。尤其面试时你可以在白板上用 O(n²) 先跑通逻辑再告诉面试官我可以通过维护单调性优化到 O(n log n)。这样沟通节奏非常自然对方也能看到你完整的思考链路。第三步才是二分优化并且在写代码之前先用口算验证一小组数据。我的习惯是拿 [3,2,4,1] 这类短序列手推一遍 tails 的变化过程确认 pos 定位正确之后再落代码。手推过程大概是3 来了tails 为空追加 32 来了bisect_left([3],2) 指向 0更新为 [2]4 来了bisect_left([2],4) 指向末尾追加 [2,4]1 来了bisect_left([2,4],1) 指向 0更新 [1,4]最后长度 2。这和预期完全一致。还有一个小技巧如果你担心 bisect_left 和 bisect_right 用混可以构造一个全是相等元素的序列去测。全相等的序列在“非递增”版本下答案必须是 1在“严格递减”版本下答案必须是 n。拿这个极端用例一跑函数的边界写没写对立刻暴露。这道题看起来短小背后覆盖的知识点却很密序列覆盖、贪心证明、二分边界、偏序和链覆盖、和区间调度模型的对比。把这些点拆开消化掉以后再遇到类似的“最少系统/最少房间/最少资源”问题你就能直接识别出套路而不是每次都在猜边界条件了。

导弹打飞机贪心算法：最少拦截系统与偏序链覆盖详解

相关推荐

OpenCore Legacy Patcher 指南：老 Mac 装新 macOS 的完整流程

3D模型渲染从建出来到渲染对：计算机图形学原理与实操排查指南

Haar特征计算过程详解：从积分图原理到手算示例与代码实战

更多资讯

ViT图像分类实战：猫狗分类任务中的Patch切分与微调技巧

JavaWeb学生成绩管理系统：Servlet+JSP+JDBC三层架构实战解析

MCreator 基岩版方块模型完全指南：Normal / Cross / 单纹理 / 自定义 `.geo.json` 模型的选择与渲染原理

instagram-private-api 内联子评论响应结构详解：MediaInlineChildCommentsFeedResponseChildCommentsItem 接口深度剖析

Calibre 电子书格式转换：3 次点击，让书进库就能发到任何阅读器

Flink CDC 同步达梦数据库：日志解析实现实时同步实践

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？