当前位置：首页 > news >正文

面试官爱问的‘导弹拦截’问题：如何用O(n²) DP和O(n log n)贪心搞定它？

news 2026/5/23 1:43:28

面试官爱问的‘导弹拦截’问题：如何用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)

典型测试场景：