“拦截导弹”这四个字在我刷题生涯里分量很重。它表面上是一道“最长上升子序列”模板题，实际上考了两个完全不同的东西：第一问求的是最长不上升子序列，第二问求的是贪心——或者反过来用 Dilworth 定理转成最长上升子序列。很多人折在第二问，就是因为没搞清楚“拦截系统”和“子序列”之间的映射关系。这篇文章我会把两问从原理到代码完整拆开，顺便带上跳跃游戏2这个经典贪心题做横向对比。如果你是刚开始学 LIS 和贪心的选手，这篇文章应该能帮你少踩不少坑。
1. 先把题目本质拆明白：拦截系统的限制到底是什么
1.1 为什么答案会是“最长不上升子序列”
导弹拦截问题的题面并不复杂：有一台防御系统，第一发炮弹能打到任意高度，但之后每一发炮弹的高度都不能超过前一发。现在来袭导弹按顺序飞来，每颗导弹有一个高度，问这套系统最多能拦截多少颗。
把这句话翻译成算法语言：如果系统拦截了第 i 颗导弹后还想拦截第 j 颗导弹（i < j），就必须满足 h[i] >= h[j]。也就是说，被这套系统拦截的导弹高度序列，必须是一个“不上升”的序列。所谓不上升，就是每个元素都大于等于后面所有元素，允许相等。
所以第一问“最多能拦截多少颗导弹”，本质就是在整个导弹高度序列中，找一个最长的子序列，让这个子序列里的元素按照原顺序满足“每个都不小于后一个”。这就是最长不上升子序列（Longest Non-Increasing Subsequence，LNIS）。
这里有个语义容易混淆的地方：很多同学看到“最长上升子序列”这六个字就直接套模板求上升序列，结果发现第一问都过不了。实际上题目要求的是“不上升”，不是“上升”。一字之差，问题性质就不一样。上升子序列要求严格递增，不上升子序列允许相等且方向相反，这两个问题在代码实现上差了一个取反和二分边界的选择。
1.2 第二问到底在问什么
第二问是：如果要拦截所有导弹，最少需要配备多少套这样的系统？
注意，这里不是问“需要多少发炮弹”，而是问“多少套系统”。每套系统都是一个独立的拦截火力通道，同一套系统内部必须遵循“后一发不高于前一发”的约束。换句话讲，每套系统拦截的导弹序列都是一个不上升子序列。
于是第二问变成了一个区间覆盖类问题：把整个导弹序列划分成尽可能少的若干个子序列，使得每个子序列都是不上升的。这个划分数量就是最少系统数。
这个问题之所以和第一问不一样，是因为“最多能拦多少”和“最少需要几套”是两个不同维度的优化目标。第一问是在一套系统里尽量多收，第二问是要用最少的系统把整个序列全部收完。虽然它们都和不上升子序列有关，但解法完全不同。第一问是 DP/二分，第二问可以用贪心，也可以借助组合数学里的 Dilworth 定理直接转成一个最长的严格上升子序列问题。
2. 第一问实战：从 O(n^2) 到 O(nlogn)
2.1 暴力 DP 是怎么设计的
拿到第一问，最容易想到的还是动态规划。定义 dp[i] 表示以第 i 颗导弹为结尾的最长不上升子序列长度。为什么要“以第 i 颗结尾”？因为我们想利用子序列的递推关系：如果已知前 j 颗导弹能组成一条不上升子序列，且 h[j] >= h[i]，那么把 i 接到这条子序列末尾，就得到一条以 i 结尾的更长子序列。
转移方程写出来就是：
dp[i] = max(dp[i], dp[j] + 1)，其中 j < i 且 h[j] >= h[i]
每个 dp[i] 初始化为 1，因为单颗导弹本身总是可以拦截的。最后答案取所有 dp[i] 的最大值，而不是 dp[n-1]，这一点初学者容易搞错。最长的子序列不一定以最后一颗导弹结尾，它可能藏在序列中间的某个位置。
这种写法的时间复杂度是 O(n^2)。题目如果给的 n 在 1000 以内，完全够用。但很多 OJ 上的版本数据范围会放大到 10^5 量级，这时候 O(n^2) 就会超时，必须换思路。
2.2 二分优化：把状态压缩成一个 d 数组
O(nlogn) 求 LIS 的核心思想是维护一个数组 d，d[k] 表示“长度为 k+1 的子序列中，末尾元素的最小值”。这个数组有一个非常重要的性质：在标准 LIS 问题中，d 是严格递增的；在允许相等的不下降子序列问题中，d 是非递减的。
有了这个单调性，我们就可以对每个新元素进行二分查找，决定它应该替换 d 中哪个位置的值，或者直接追加到 d 末尾。最终 d 的长度就是最长子序列的长度。
但注意，我们这里要求的是最长不上升子序列，不是最长上升子序列。直接套 LIS 模板会出错。一个简单优雅的处理方式是把所有高度取反，也就是把 h 变成 -h。取反之后，原来“不上升”的关系 h[i] >= h[j] 就变成了 -h[i] <= -h[j]，也就是说在取反后的序列上找的是“最长非下降子序列”（允许相等）。
这样我们就把一个不上升子序列问题，转化成了一个用标准二分模板能解决的“非降 LIS”问题。具体实现时，对每个取反后的元素 x，在 d 中找第一个大于 x 的位置，用 x 替换它；如果不存在这样的位置，就把 x 追加到 d 末尾。
2.3 判断等号关系：lower_bound 和 upper_bound 怎么选
这里藏着这道题最大的一个坑：到底用 lower_bound 还是 upper_bound？
标准 LIS（严格上升）用的是 lower_bound，因为严格上升不允许出现相等的连续元素。比如序列 [1, 3, 3]，最长严格上升长度是 2，而不是 3。如果用一个等于当前值的元素去替换 d 中第一个大于等于它的位置，就能保证 d 中不会出现连续相等的情况，从而保证子序列严格上升。
而取反后我们要求的是“非下降子序列”，它是允许相等的。举个例子，原高度序列 [5, 5]，取反后是 [-5, -5]，这两个元素可以组成一个长度为 2 的非下降子序列。这种情况下必须用 upper_bound，也就是找第一个大于当前值的位置。如果错误地用 lower_bound，遇到相等元素时会把它替换到相同位置上，导致 d 无法正常增长，答案被低估。
判断标准可以记成一句话：严格上升用 lower_bound，非下降用 upper_bound。这一条同样适用于所有 LIS 变体，后面做别的题会频繁用到。
3. 第二问贪心：怎么用最少的系统拦下所有导弹
3.1 贪心策略：每次选“最能接住”的系统
第二问的经典思路是贪心模拟。我们用一组数记录当前每个系统“最近一次拦截的导弹高度”，这个值同时代表这套系统下一发炮弹能发射的最高高度。系统拦截完一颗导弹后，它的可发射高度就变成了这颗导弹的高度，因为后面的炮弹不能超过它。
当一颗新导弹 h 到来时，我们应该选择哪个系统去拦截？直觉上，应该选一个“能拦截它且当前高度最接近它的系统”。也就是说，在所有大于等于 h 的系统高度里，选最小那个。
这个贪心用代码实现很直观：用一个 multiset 维护所有系统的当前高度。对每个 h，调用 lower_bound(h)，找到最小的不小于 h 的系统高度。如果找到了，就说明有系统能接住这颗导弹，用这颗导弹的高度 h 替代原来那个系统的高度；如果找不到，说明当前所有系统都打不了这么高的导弹，只能新开一套系统。
这个策略的直观理解是“不要把高射炮浪费在低空目标上”。一个当前高度 300 的系统和一个当前高度 200 的系统，都能拦截高度 100 的导弹，但你让 300 去拦，这系统以后就只剩 100 的高度了；让 200 去拦，300 还留着，未来还能处理更高的目标。
3.2 为什么选最接近的而不是随便一个能拦截的
要证明贪心选最接近的确实是最优的，可以用交换论证。
假设某个最优方案里，高度 h 的导弹被系统 A 拦截了，而贪心算法选择的是系统 B，且 B 的当前高度比 A 更低、更接近 h。我们知道 B 是能拦住 h 的，因为它也满足“高度不小于 h”。现在我们做一个交换：让 B 去拦 h，让 A 去承担原本 B 要拦截的后续任务。由于 A 本身高度更高，它能覆盖的导弹范围更广，所以原方案里 B 能处理的后续导弹，A 也一定处理得了。这样一来，交换后的方案仍然合法，而且系统数量没有增加。
这个论证说明，贪心选择最低可用的系统不会把局面变差。每一步都保持“系统高度集合”在某种意义上最优，最终得到的系统数量就是最小值。
这里还有一个极容易踩的坑：有人会想当然地选择“当前高度最高的系统”，也就是用 upper_bound 找一个尽量大的系统去接。这个想法初看好像也没问题，反正都能接住，但实际会很快把高系统全部拉低，导致后面来一个中等高度的导弹时无系统可用，被迫新开系统。实测中这种做法会多开很多套系统，完全错误。
3.3 Dilworth 定理：把贪心题变成 LIS 题
第二问除了贪心模拟，还有一条更数学化的路：Dilworth 定理。这个定理在偏序集上说了一件很漂亮的事：一个偏序集里，最小链覆盖数等于最大反链长度。
把它映射到导弹拦截问题里，需要先定义偏序关系。我们把每颗导弹看作一个元素，定义元素 i “小于等于”元素 j 当且仅当 i 在导弹序列中排在 j 前面，并且 h[i] >= h[j]。在这样的偏序关系下，一条“链”就是一组满足“后一个永远不高于前一个”的导弹子序列，这正好对应一套系统能拦截的序列。链覆盖就是若干套系统覆盖全部导弹。那“反链”是什么呢？反链里的任意两个元素都不能比较，也就是说任意两颗导弹，谁也不能排在谁后面还满足高度不小于它。这意味着反链中元素的高度是严格递增的，而且位置也是严格递增的，所以反链就是一个严格上升子序列。
于是 Dilworth 定理告诉我们的结论就是：严格上升子序列的长度，恰恰等于最少需要的链覆盖数。第二问的答案正是“最长严格上升子序列”的长度。
这个结论好用到离谱：第二问直接用标准 LIS 模板算，连贪心模拟都不需要。而且代码和第一问惊人地像，区别只在第一问要取负后用 upper_bound，第二问直接用 lower_bound 求严格上升。很多人第一次看到这个对应关系时会觉得不可思议，但理解了偏序结构之后就顺理成章了。
4. 完整代码与调试实录
4.1 可直接 AC 的 C++ 实现
把两问合在一起写，代码并不长。注意题目输入格式有的是第一行给导弹数量 n，第二行给高度；有的是不告诉 n，直接一行或多行读到文件尾。我写的版本按“读到EOF”处理，兼容性更好。
#include <bits/stdc++.h> using namespace std; int main() { vector<int> a; int x; while (cin >> x) a.push_back(x); int n = a.size(); if (n == 0) return 0; // 第一问：最长不上升子序列 // 取反后变成最长非下降子序列，使用 upper_bound vector<int> d; for (int i = 0; i < n; i++) { int v = -a[i]; auto it = upper_bound(d.begin(), d.end(), v); if (it == d.end()) d.push_back(v); else *it = v; } cout << d.size() << endl; // 第二问：最长严格上升子序列，使用 lower_bound vector<int> d2; for (int i = 0; i < n; i++) { int v = a[i]; auto it = lower_bound(d2.begin(), d2.end(), v); if (it == d2.end()) d2.push_back(v); else *it = v; } cout << d2.size() << endl; return 0; }这段代码核心就两个二分操作。第一问先取负再求非降，第二问直接求严格上升。如果你理解了前面的原理，代码基本就是“翻译”过程。
4.2 最容易踩的等号细节坑
我在实际帮人 review 这道题的代码时，发现错误几乎都集中在“等号”上。
第一个坑：第一问忘了取负。如果不取负，直接在原数组上维护一个数组做“不上升”二分，逻辑上等价于在一个反转后的数组上求 LIS，但二分条件非常绕，很容易写错。取负是降低心智负担的推荐做法。
第二个坑：第一问用了 lower_bound。取负后要求允许相等，用 lower_bound 会把相等值替换到同一个位置，导致 d 的长度偏小。验证方法很简单：输入“5 5”，正确答案是 2，如果输出 1 就是等号边界错了。
第三个坑：第二问用了 upper_bound。第二问要求严格上升，反过来如果允许相等，会把严格上升子序列长度算大。举个例子，输入“1 2 2”，正确答案是最少 2 套系统，因为两颗高度 2 的导弹可以被同一套系统拦截（后一发不高于前一发，等于也允许）。但如果你用 upper_bound 求不下降子序列，会得到长度 3，直接算错。
这三个坑本质上都是同一个问题：没搞清楚“等于”在这种题目里意味着什么。导弹拦截允许连续两发高度相同，不上升子序列允许相等，严格上升不允许相等。对应到二分函数上就是 upper_bound 和 lower_bound 的区别。
4.3 输入格式与数据范围的坑
我见过不少人在这道题的 IO 上翻车。一些版本会在第一行给导弹数量 n，第二行给 n 个高度；另一些版本没有任何 n，直接给高度直到文件结束。如果你按照第一种格式写 while(cin >> x)，当第二行读完所有高度后，cin 读到 EOF 会自然退出，两种格式都能兼容。反过来，如果你先 cin >> n 再读 n 个，遇到不给定 n 的版本就只能读到第一个数然后就断掉，直接 WA。
数据范围方面，经典题 n 可能只有 1000，O(n^2) DP 能过；但很多集训队题目或者 OJ 加强版会把 n 放到 10^5 甚至更大。这时候必须用 O(nlogn) 的二分写法。我建议即使 n 很小，也直接写二分版本，养成习惯，以后遇到数据范围变异题型不用改代码。
还有一个小细节：multiset 贪心版本中，删除元素时要用 erase(it) 删除迭代器指向的那一个元素，而不是 erase(h)，后者会把所有等于 h 的元素都删掉。如果你维护的是 multiset，两个系统高度相同是完全合法的，例如两个系统当前高度都是 200，一颗 150 的导弹来了，只会把一个系统降为 150，另一个必须保留。用 erase(h) 会全删，系统数量就错乱了。
5. 贪心思路的延伸：跳跃游戏2为什么也是贪心
5.1 跳跃游戏2的贪心策略拆解
导弹拦截第二问能帮我们理解贪心，但很多同学对贪心还是不熟，因为这套“选最接近”的思路和常见的“选最远”的贪心感觉不太一样。换个题型对比一下会更清晰，这里就拿跳跃游戏2说事。
跳跃游戏2的题面是：给定一个非负整数数组 nums，你一开始在下标 0，nums[i] 表示你在下标 i 处最多能向后跳多远。求跳到最后一个下标所需的最少跳跃次数。
这个问题的贪心思路是维护两个边界：当前一步能到达的最远位置 curEnd，以及在 [0, curEnd] 范围内能得到的最远下一跳 far。遍历数组，不断用 i + nums[i] 更新 far；当 i 走到 curEnd 时，说明这一步能覆盖的区间到头了，必须跳出去，于是步数加一，把 curEnd 更新为 far。
实现代码是很多人背过的模板：
int jump(vector<int>& nums) { int n = nums.size(); int steps = 0, curEnd = 0, far = 0; for (int i = 0; i < n - 1; i++) { far = max(far, i + nums[i]); if (i == curEnd) { steps++; curEnd = far; } } return steps; }为什么这个贪心是对的？可以把它理解成分层 BFS：第 k 步能到达的所有位置构成一层，far 就是下一层能达到的最右边界。因为每层的可达范围是连续的，而且 newFar 是层内所有位置能跳到的最远值，所以用它扩大范围绝不会漏掉更短解。每一层内部所有位置都已经在当前步可达，跨到下一层只需多加一步，因此层数即最少步数。
5.2 两类经典贪心的共性思考
导弹拦截第二问和跳跃游戏2放在一起，能看出贪心算法的两个侧面。
导弹拦截的策略是“保守型贪心”：在满足条件的所有系统中，选对后续影响最小的那个，也就是末尾高度最小的系统，尽可能保留高系统的潜力。它优化的是“资源的浪费”，把消耗压低，从而减少总资源数。
跳跃游戏2的策略是“激进型贪心”：在当前位置能到达的所有跳点中，选能把下一跳边界推得最远的那个，最大化每一步覆盖的范围。它优化的是“覆盖的扩张”，把每一步的收益拉满，从而减少总步数。
这两个策略表面上方向相反，本质上都是同一个思想：局部选择一个对全局最有利的状态，并证明该选择不会给后续决策带来额外成本。做贪心题的时候，不要上来就想“选最大还是选最小”，而是想“这个选择会不会损害我未来的选择空间”。破坏未来的选择空间，通常就是贪心出错的信号；不损害未来选择空间，往往就是贪心的正确答案。
我自己的刷题体会是，贪心题最难的不是实现，而是建立信心。拿到导弹拦截第二问，如果你只是“感觉”要选最接近的系统，那还不足以说服自己。试着像前面那样做一个交换论证，或者拿它和 Dilworth 定理相互印证，心里就踏实了。以后再遇到类似的资源分配类题目，你就会习惯性地先问自己：我选的这个局部最优，会不会牺牲掉后面更有价值的可能性？想清楚这一点，比多刷几十道模板题更有用。
