 DP和O(n log n)贪心搞定它？)
面试官爱问的‘导弹拦截’问题：如何用O(n²) DP和O(n log n)贪心搞定它？
在技术面试中，系统设计类问题往往能考察候选人的算法思维和问题解决能力。"导弹拦截"问题就是这样一个经典案例，它不仅考察动态规划的应用，还涉及贪心算法的优化思路。本文将带你从问题理解到代码实现，完整梳理这道题的解决路径。
1. 问题理解与建模
导弹拦截问题的核心可以抽象为两个子问题：
- 单系统最大拦截量：求导弹高度序列的最长非递增子序列长度
- 全拦截最小系统数：求能将所有导弹分成的最少非递增子序列数
举个例子，对于输入序列389 207 155 300 299 170 158 65：
- 最长非递增子序列是
389 300 299 170 158 65，长度为6 - 最少需要2套系统，分组方式可以是：
- 系统1：389 207 155 65
- 系统2：300 299 170 158
注意：这里"非递增"指允许相等，即对于序列中的元素a[i]和a[j]，当i<j时，a[i]≥a[j]
2. 动态规划解法（O(n²)）
2.1 最长非递增子序列
这是典型的线性DP问题。定义状态f[i]表示以第i个导弹结尾的最长非递增子序列长度，状态转移方程为：
f[i] = max(f[j] + 1) for j in range(i) if h[j] >= h[i]实现代码示例：
def max_interception(h): n = len(h) f = [1] * n for i in range(1, n): for j in range(i): if h[j] >= h[i]: f[i] = max(f[i], f[j] + 1) return max(f)2.2 复杂度分析
- 时间复杂度：O(n²) —— 双重循环
- 空间复杂度：O(n) —— 存储f数组
当n≤1000时，这个解法完全可行。但面试官可能会追问："如果n扩大到10⁵呢？"
3. 贪心优化解法（O(n log n)）
3.1 最少系统数的贪心策略
这个问题等价于求导弹高度序列的"最小非递增子序列划分"，可以通过维护一个系统数组g[]，其中g[i]表示第i个系统当前能拦截的最低高度。
算法步骤：
- 初始化空数组g，cnt=0
- 对于每个导弹高度h：
- 在g中找到第一个≥h的最小索引k（二分查找）
- 如果找到，更新g[k]=h
- 否则，将h加入g末尾，cnt+1
3.2 代码实现
import bisect def min_systems(h): g = [] for x in h: idx = bisect.bisect_right(g, -x, lo=0, hi=len(g)) if idx < len(g): g[idx] = -x else: g.append(-x) return len(g)技巧：通过存储-x来利用Python的bisect模块实现降序查找
3.3 复杂度分析
- 时间复杂度：O(n log n) —— 每个元素一次二分查找
- 空间复杂度：O(n) —— 存储g数组
4. 面试中的实战技巧
4.1 沟通策略
明确问题：先确认输入输出格式、边界条件
- "请问导弹高度都是正整数吗？"
- "系统数量的定义是否需要考虑空情况？"
分步阐述：
- 先给出暴力解法，再讨论优化
- "对于第一个问题，我想到可以用动态规划..."
- "这个解法时间复杂度是O(n²)，如果数据量更大，可以考虑..."
4.2 常见Follow-up问题
数据范围扩大时如何优化？
- 最长非递增子序列也有O(n log n)解法（类似耐心排序）
如果导弹有不同价值，如何最大化拦截价值？
- 变为带权LIS问题，可用树状数组优化
实时处理场景下的解决方案？
- 考虑在线算法设计
5. 代码模板与测试用例
完整解决方案模板：
def missile_interception(h): # 最长非递增子序列 def lis(): # O(n²) DP实现 pass # 最少系统数 def min_sys(): # O(n log n)贪心实现 pass return lis(), min_sys() # 测试用例 test_case = [389, 207, 155, 300, 299, 170, 158, 65] print(missile_interception(test_case)) # 应输出 (6, 2)典型测试场景：
| 测试案例 | 预期输出 | 说明 |
|---|---|---|
| [100, 90, 80, 70] | (4, 1) | 完全递减 |
| [1, 2, 3, 4] | (1, 4) | 完全递增 |
| [1, 1, 1, 1] | (4, 1) | 全部相等 |
| [] | (0, 0) | 空输入 |
6. 算法背后的数学原理
这个问题实际上展示了Dilworth定理的应用：对于任何有限偏序集，其最小反链划分等于最长链的长度。在本题中：
- 偏序关系：导弹高度的非递增关系
- 反链划分：每个系统拦截的导弹序列
- 最长链：最长非递增子序列
理解这层关系可以帮助我们更好地把握问题的本质，在面对变种问题时也能快速找到解决方向。
