求O(mlog(n))时间内不修改原栈输出m个最小元素的算法

实现步骤 #

1. 复制栈元素并还原原栈

   • 创建临时栈temp，将原栈A的所有元素逐个弹出压入temp，同时把这些元素存入数组arr中。
   • 再将temp里的元素逐个弹回原栈A，确保原栈的结构和元素顺序完全不变。这一步耗时O(n)。

2. 构建小顶堆

   • 将数组arr中的元素堆化为小顶堆，堆化操作的时间复杂度为O(n)，属于预处理步骤。

3. 提取并打印m个最小元素

   • 重复m次以下操作：
     • 弹出堆顶元素（当前堆内的最小值）并打印。
     • 将堆的最后一个元素移到堆顶，执行下沉调整以维持小顶堆性质，每次调整耗时O(logn)。
   • 这一步总耗时O(mlogn)。

复杂度说明 #

整体时间复杂度为O(n + mlogn)，当m与n规模接近时，整体复杂度等价于O(mlogn)；若m远小于n，预处理的O(n)会占主导，但这类问题中预处理通常是被允许的，算法完全满足题目要求。

针对小m的优化方案 #

如果m远小于n，还可以用大小为m的大顶堆优化：

• 遍历数组arr的每个元素：
  • 堆内元素数量不足m时，直接将当前元素加入堆（O(logm)时间）。
  • 若当前元素小于堆顶元素，弹出堆顶并将当前元素加入堆（O(logm)时间）。
• 遍历结束后，堆内存储的就是m个最小元素，将堆元素逐个弹出后反转，即可得到从小到大的顺序并打印。
• 该方案时间复杂度为O(nlogm)，当m远小于n时，比O(mlogn)更高效。

内容的提问来源于stack exchange，提问作者Eli7