从导弹拦截到贪心算法：LeetCode 1010题保姆级图解教程（附C++代码）

想象你是一名防空指挥官，面对屏幕上不断跳动的导弹高度数据，必须在瞬间做出决策：是用现有拦截系统迎击，还是紧急启动备用设备？这不仅是军事模拟中的经典场景，更是算法竞赛中贪心策略的绝佳案例。本文将用"导弹拦截"这一生动故事，带你穿透抽象算法概念，掌握LeetCode 1010题的核心解法。

1. 问题本质的双重解读

导弹拦截问题看似复杂，实则包含两个相互关联的子问题：

1. 单系统最大拦截量 ：相当于寻找最长非上升子序列（Longest Non-Increasing Subsequence）
2. 全拦截最小系统数 ：本质是求解序列的最小链划分，等价于寻找最长上升子序列长度

这两个问题在算法领域被称为 Dilworth定理 的经典应用。理解这层关系，就能将看似不同的两个问题统一在同一个框架下分析。

关键洞察：拦截系统的特性（后发导弹高度≤前发）恰好定义了非上升序列，而系统间的独立性则对应序列划分的无关性。

2. 最长非上升子序列的DP解法

我们先解决第一个问题——单系统最多能拦截多少导弹。用动态规划可以这样建模：

定义 dp[i] 表示以第 i 枚导弹结尾的最长非上升子序列长度。状态转移方程为：

for (int j = 0; j < i; j++) {
    if (h[i] <= h[j]) {
        dp[i] = max(dp[i], dp[j] + 1);
    }
}

操作步骤详解 ：

1. 初始化所有 dp[i] = 1 （每个导弹自身构成长度为1的序列）
2. 对于每个导弹 i ，检查前面所有导弹 j ：
   • 如果 h[i] ≤ h[j] ，说明 i 可以接在 j 后面
   • 更新 dp[i] 为 dp[j]+1 的最大值
3. 最终结果是所有 dp[i] 中的最大值

时间复杂度分析 ：

• 外层循环 n 次，内层循环平均 n/2 次
• 总复杂度为O(n²)，对于n≤1000完全可行

3. 最小系统数的贪心策略

第二个问题要求拦截所有导弹所需的最少系统数，这里展现出 贪心算法 的精妙：

1. 维护一个数组 sys 记录各系统当前拦截的最低高度
2. 对于每枚导弹，寻找能拦截它的最低高度系统：
   • 存在可用系统：更新该系统高度为当前导弹高度
   • 无可用系统：新增系统，记录当前高度

int cnt = 0; // 系统计数
vector<int> sys; // 各系统当前拦截高度

for (int height : missiles) {
    auto it = lower_bound(sys.begin(), sys.end(), height, greater<int>());
    if (it != sys.end()) {
        *it = height;
    } else {
        sys.push_back(height);
        cnt++;
    }
}

贪心选择正确性证明 ：

• 每次选择可用的最小高度系统，保留较高系统应对后续可能的高空导弹
• 这种策略确保系统利用率最大化，与建立上升子序列的过程等价

4. 算法优化与边界处理

原始解法有优化空间，特别是第二个问题可以利用STL简化：

优化后的双解法代码框架 ：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve() {
    vector<int> missiles;
    int height;
    while (cin >> height) missiles.push_back(height);
    
    // 问题一：最长非上升子序列
    vector<int> dp(missiles.size(), 1);
    int max_len = 1;
    for (int i = 1; i < missiles.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (missiles[i] <= missiles[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    
    // 问题二：最小系统数（贪心）
    vector<int> systems;
    for (int h : missiles) {
        auto it = lower_bound(systems.begin(), systems.end(), h, greater<int>());
        if (it != systems.end()) *it = h;
        else systems.push_back(h);
    }
    
    cout << max_len << endl << systems.size() << endl;
}

常见踩坑点 ：

1. 输入处理：注意导弹高度可能是单行空格分隔的字符串
2. 等值处理：高度相等时仍可拦截（非严格下降）
3. 空输入：需考虑边界情况

5. 可视化理解与思维训练

为了加深理解，我们通过具体案例拆解：

导弹序列 ：389, 207, 155, 300, 299, 170, 158, 65

问题一求解过程 ：

导弹	389	207	155	300	299	170	158	65
dp值	1	2	3	2	3	4	5	6

问题二系统变化 ：

1. 389 → 系统A[389]
2. 207 → A[207]
3. 155 → A[155]
4. 300 → 需要新系统B[300]
5. 299 → B[299]
6. 170 → A[170]
7. 158 → A[158]
8. 65 → A[65]

最终系统数：2（A和B）

6. 从特例到通用的思维跃迁

理解这个案例后，可以推广到更一般的场景：

1. 调度问题 ：类似的任务调度、课程安排等问题都可转化为此类模型
2. 序列分析 ：股票分析中的波段识别、DNA序列匹配等都有相似结构
3. 系统设计 ：资源分配、负载均衡等实际问题可借鉴这种贪心策略

在ACM竞赛中，这类问题常有以下变种：

• 要求输出具体拦截方案而非仅数量
• 导弹高度带时间窗口限制
• 系统有启动成本时的最优成本控制

7. 代码实现细节与调试技巧

完整可提交的AC代码需要特别注意：

输入处理优化 ：

string line;
getline(cin, line);
istringstream iss(line);
vector<int> missiles;
int height;
while (iss >> height) missiles.push_back(height);

调试建议 ：

1. 先验证最长子序列计算是否正确
2. 打印系统数组观察其变化过程
3. 对极端用例测试：
   • 严格递减序列（应输出n和1）
   • 严格递增序列（应输出1和n）
   • 全部等高的序列

性能分析工具 ：

g++ -pg solution.cpp -o solution
./solution < input.txt
gprof solution gmon.out > analysis.txt

8. 扩展思考：为什么贪心在此有效

这个问题的精妙之处在于它展现了贪心算法适用的典型场景：

1. 最优子结构 ：全局最优解包含局部最优解
2. 无后效性 ：当前决策不影响后续决策环境
3. 单调性 ：系统数组始终保持有序，便于二分查找

与其他贪心经典问题（如区间调度、霍夫曼编码）对比，可以发现共同特征：

• 都需要某种排序预处理
• 都维护一个关键数据结构（这里是系统高度数组）
• 决策只依赖当前状态而非历史路径

在实际工程中，这种模式可应用于：

• 云资源的自动扩缩容
• 实时系统中的任务调度
• 网络流量中的拥塞控制