每周挑战391中的两个优化任务
内容提要
文章探讨两个算法问题：一是合并两个有序数组求中位数，比较了朴素排序法（简洁但耗内存）、滑动窗口法（内存高效但较慢）及利用列表切片的优化版；二是堆叠盒子问题，按宽度排序后提取深度，用动态规划扩展序列，仅记录每个序列末尾元素以降低内存，处理千个盒子约需一秒。
延伸解读
算法选择需权衡时间与内存
文章比较了求两个有序数组中位数的三种方法。朴素排序法代码简洁但需合并整个数组，内存占用高；滑动窗口法仅存储两个元素，内存高效，但基准测试显示其速度比朴素法慢一倍以上；优化版利用列表切片，速度最快，但内存消耗与朴素法相当。因此，若数组极大无法全部载入内存，滑动窗口法是唯一选择；否则优化版在速度上更优。
堆叠盒子问题的动态规划优化
堆叠盒子问题要求找出能依次嵌套的最大盒子数。文章先按宽度升序、同宽按深度降序排序，然后提取深度序列，问题转化为求最长严格递增子序列。初始动态规划记录所有可能序列，内存消耗大；优化后仅记录每个序列的末尾元素，大幅降低内存，处理1000个盒子约需一秒。
排序策略避免同宽盒子误选
在堆叠盒子问题中，排序时对相同宽度的盒子按深度降序排列，确保在深度序列中，同宽盒子的深度不会形成递增关系，从而避免将两个同宽盒子放入同一嵌套序列。这一细节保证了算法的正确性，因为盒子必须严格小于另一个盒子才能嵌套。
Q&A
合并两个有序数组求中位数，有哪些实现方法？各有什么优缺点？
文章介绍了三种方法：1. 朴素排序法：直接合并排序后取中位数，代码简洁但需要存储整个合并数组，内存消耗大；2. 滑动窗口法：用大小为2的窗口在合并过程中滑动，只需存储两个元素，内存高效但速度较慢；3. 优化版：利用列表切片只取中位数所需的元素，避免存储整个排序列表，速度最快。
为什么滑动窗口法求中位数比朴素排序法慢？
滑动窗口法需要手动管理两个数组的索引和窗口位置，代码复杂且循环中条件判断多，导致执行效率低。基准测试显示，滑动窗口法每秒处理111次，而朴素排序法每秒292次，滑动窗口法比朴素排序法慢约62%。
在什么情况下应该使用滑动窗口法求中位数？
当两个数组非常大，无法一次性合并到内存中时，滑动窗口法是最佳选择。因为它只需要存储两个元素和少量变量，内存占用极低，适合内存受限的环境。
如何优化朴素排序法求中位数以减少内存使用？
优化方法是使用列表切片：先对合并后的数组排序，但只通过切片取出中位数所需的一个或两个元素，而不是将整个排序结果存储到数组中。这样既保持了排序的简洁性，又大幅减少了内存占用，同时速度比朴素法更快。
堆叠盒子问题的基本解决思路是什么？
首先按宽度升序排序盒子，若宽度相同则按深度降序排序。然后提取深度序列，问题转化为在深度序列中寻找最长递增子序列。通过动态规划逐步扩展序列，记录每个序列的末尾元素，最终得到最大堆叠数量。
堆叠盒子问题中如何降低内存消耗？
不需要存储完整的序列，只需记录每个序列的最后一个元素。在每一步中，基于当前所有序列的末尾元素，尝试用后续盒子扩展，生成新的末尾元素集合。这样内存占用仅与盒子数量成正比，处理1000个盒子约需一秒。
