栈实现take函数遇异常：第三次插入后无法返回中间值求助

嘿，我来帮你捋捋这个问题！你要写的take函数核心是每次接收一个int，返回当前所有插入值的中位数（也就是中间数值），还要尽可能省内存，用栈实现时第三次插入后出问题了对吧？

先说说你用栈实现可能踩的坑 #

栈本身是后进先出的结构，单纯用栈很难直接维护中位数——因为中位数需要知道元素的排序状态，而栈不支持随机访问。如果你的代码没维护一个有序栈，或者维护有序栈的逻辑出错，就会导致第三次插入后取错中间值：

• 比如插入时没把元素放到正确的位置，栈里的元素是乱序的，取中间值时自然不对；
• 就算维护了有序栈，取中间值时的元素移动逻辑也容易错：第三次插入后总共有3个元素，中间索引是1（0开始），如果你的代码弹出元素的次数不对（比如弹了2次而不是1次），就会取到栈底或者栈顶的错误元素。

修正栈实现的思路（如果一定要用栈） #

要让栈能正确返回中位数，必须维护一个始终有序的栈，每次插入时把元素放到合适的位置，取中位数时临时移动元素找到中间值再恢复栈。给你写个伪代码参考：

// 两个栈：主栈存有序元素，临时栈用于插入和取中位数时的元素中转
stack mainStack
stack tempStack

function take(int num):
    // 第一步：把当前元素插入到有序位置
    while mainStack 不为空 且 mainStack.top() > num:
        tempStack.push(mainStack.pop())
    mainStack.push(num)
    // 把临时栈的元素放回主栈
    while tempStack 不为空:
        mainStack.push(tempStack.pop())
    
    // 第二步：计算并取出中位数
    n = mainStack.size()
    midIndex = (n - 1) // 2  // 0-based索引，3个元素时就是1
    // 把前midIndex个元素移到临时栈
    for i from 0 to midIndex - 1:
        tempStack.push(mainStack.pop())
    midValue = mainStack.top()
    // 恢复主栈的有序状态
    while tempStack 不为空:
        mainStack.push(tempStack.pop())
    
    return midValue

你可以对照自己的代码看看：是不是插入时没做有序处理？或者取中位数时的循环次数错了？比如第三次插入后midIndex是1，循环应该执行1次（把第一个元素移到临时栈），然后取mainStack的top就是中间值。

更省内存&高效的优化方案（不用栈） #

其实如果追求最少内存+高效，栈并不是最优选择——因为每次插入和取中位数都要移动大量元素，内存开销（临时栈）也不小。更合适的是用两个堆：

• 一个大顶堆存较小的一半元素，堆顶是这一半的最大值；
• 一个小顶堆存较大的一半元素，堆顶是这一半的最小值；
• 始终保持大顶堆的大小等于小顶堆，或者比小顶堆多1，这样大顶堆的堆顶就是中位数（奇数个元素时）。

用C++实现的示例代码如下：

#include <queue>
using namespace std;

// 大顶堆：存较小的一半元素，堆顶是当前最小半区的最大值
priority_queue<int> maxHeap;
// 小顶堆：存较大的一半元素，堆顶是当前最大半区的最小值
priority_queue<int, vector<int>, greater<int>> minHeap;

int take(int num) {
    // 把元素插入到对应的堆
    if (maxHeap.empty() || num <= maxHeap.top()) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }

    // 平衡两个堆的大小，保证maxHeap最多比minHeap多1个元素
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size()) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }

    // 直接返回大顶堆的堆顶就是中位数
    return maxHeap.top();
}

这个方案内存占用最少，因为不需要额外的临时存储来维护有序序列，堆的内部实现也比栈的频繁移动更高效，每次插入和取中位数都是O(logn)的时间复杂度。

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