Meta Quack排序：随机两端弹出与重复段判向

题目重点：Quack每次随机弹出当前最小或最大值，利用下一个不同值判定上一段来自哪端，线性恢复有序结果。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

Quack初始内部按值排序，pop每次只能移除当前最小或最大值；不观察具体随机端。训练返回升序列表并消耗原Quack。
只调用size/pop，假设接口单次O(1)；如果底层数组头删为O(n)，总运行成本需把接口实际成本计入。重复值允许，输入不必唯一。

解题路线

相邻两次弹出的不同值x/y给判向：若x<y，则x不可能是当时最大值，因为y那时仍在结构里；x必来自最小端。若x>y，则x来自最大端。
相等时无法立刻判断，把连续相等值暂存为(pending,count)，直到下一个不同值出现再整体判向。相同段即使实际先后从两端弹，值等价，最终放同端仍正确。
判为最小端的段依次append到lower，它们非降；判为最大端的段append到upper，它们非升。最后未决等值段处于所有lower与upper之间，结果lower+pendingRun+reverse(upper)。
此方法无需reinsert或额外sort；每元素pop一次，证明靠Quack“两端极值”合同，而不是随机性或平均情况。独立测试穷举每种min/max弹出轨迹，重复值也覆盖。

手动走一遍

Quack=[1,2,2]，弹出2/2/1。若看到2==2就把前2当最小，会得错序；正确先保留两张2，见1后判该段为最大端，lower为空，最后1夹在前，reverse upper得[2,2]，最终[1,2,2]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def sorted_quack(quack):
    """Consume an initially sorted Quack: pop removes either current minimum or maximum.

    Only size()/pop() are used. Equal popped values are held until the next distinct
    value resolves which end they belong to. Return all values sorted ascending.
    Assumes each interface call is O(1); reinsert is unnecessary.
    """
    lower=[];upper=[];pending=None;count=0
    while quack.size():
        value=quack.pop()
        if count==0:
            pending=value;count=1
        elif value==pending:
            count+=1
        else:
            if pending<value:
                lower.extend([pending]*count)
            else:
                upper.extend([pending]*count)
            pending=value;count=1
    return lower+([pending]*count if count else [])+upper[::-1]

复杂度

恰好n次pop、n+1次size，算法工作O(n)，lower/upper/结果总O(n)空间。如果pop/size接口成本分别P/S，总时间O(n(P+S))，不能忽略底层实现。

易错点与追问

容易失分的边界

相等值不能直接判成最小端或最大端，必须延迟到不同值或结束。
若pop可弹任意内部元素，邻值大小判向不成立，算法合同必须极值两端。
upper收集为降序，最后不反转会把高值尾段排错。

继续深挖

要求不消耗Quack时需恢复元素，但insert成本可能增加；先明确接口是否允许复制或遍历。
空结构返回[]，全相同只剩最后pending段，仍正确；值为NaN会破坏比较全序，需要拒绝或定义顺序。