Louis Aeilot's Blog
·
題解 導彈攔截
💡
原文中文，约1800字，阅读约需5分钟。
📝
内容提要
本文讨论了导弹拦截问题的解决方案，主要通过求解最长不上升序列和上升序列的长度。使用STL中的lower_bound和upper_bound函数，结合栈结构，分别实现O(n)和O(nlogn)的算法。通过遍历导弹高度，更新栈以获取所需序列长度，最终输出结果。
🎯
关键要点
- 本文讨论了导弹拦截问题的解决方案，主要通过求解最长不上升序列和上升序列的长度。
- 使用STL中的lower_bound和upper_bound函数，结合栈结构，分别实现O(n)和O(nlogn)的算法。
- 遍历导弹高度，更新栈以获取所需序列长度，最终输出结果。
- 在求解过程中，若导弹高度小于等于栈顶元素，则直接入栈；若大于栈顶元素，则覆盖栈内第一个小于它的元素。
- 上升序列的求解与不上升序列类似，但使用upper_bound函数处理相同高度的导弹。
❓
延伸问答
导弹拦截问题的主要解决方案是什么？
主要通过求解最长不上升序列和上升序列的长度来解决。
在求解导弹拦截问题时使用了哪些算法？
使用了O(n)和O(nlogn)的算法。
如何使用STL中的lower_bound和upper_bound函数？
lower_bound用于求序列中第一个大于等于某个数的数，upper_bound用于求第一个大于某个数的数。
在求解不上升序列时，如何处理导弹高度？
遍历导弹高度，若高度小于等于栈顶元素则入栈，若大于则覆盖栈内第一个小于它的元素。
上升序列的求解与不上升序列有什么不同？
上升序列使用upper_bound函数处理相同高度的导弹，而不上升序列使用lower_bound函数。
最终输出的结果是什么？
输出的是最长不上升序列和上升序列的长度。
➡️
