DoorDash Local Peak：每轮处理最小的相邻峰值订单

题意与假设

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

• 训练契约把 order_ids 视为互异整数；题目示例是 [3,5,1,4,2]，未说明重复 ID 的决胜规则，因此示例代码拒绝重复值。
• 当前活跃序列中的元素若严格大于所有存在的相邻元素就是 eligible；端点只与一个邻居比，单元素自动 eligible。每轮从所有 eligible 中选数值最小的订单 ID 并删除。
• 不把题目的手绘 -1 标记直接当删除语义；逻辑邻接必须跳过所有已删除位置。

解题路线

1. 用两个数组 left/right 模拟双向链表，表示当前活跃序列中每个位置的左右邻居。初始化扫描所有 eligible 位置，按 (order_id,index) 放入小根堆。
2. 每轮弹出堆顶并重新核验它仍存活且 eligible，处理后把左右邻居连起来。只有这两个邻居的 eligible 状态可能变化，因此重新检查并入堆。
3. 允许堆中有旧候选或同一位置的重复候选，以 alive 与实时邻居检查惰性过滤；因为 ID 互异，小根堆顶的有效项就是当前最小 eligible。

手动走一遍

[3,5,1,4,2] 初始峰值 5、4，先删 4，得到 [3,5,1,2]；再删新峰值 2；然后依次删 5、3、1，返回 [4,2,5,3,1]。这是题目公开的完整例子。

Python 参考实现

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

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

"""Remove the smallest currently eligible local maximum."""

from heapq import heappop, heappush


def processing_order(order_ids: list[int]) -> list[int]:
    """Assume distinct IDs; an endpoint has its sole neighbor."""
    n = len(order_ids)
    if len(set(order_ids)) != n:
        raise ValueError("order IDs must be distinct")
    left = [i - 1 for i in range(n)]
    right = [i + 1 for i in range(n)]
    alive = [True] * n
    heap: list[tuple[int, int]] = []

    def eligible(i: int) -> bool:
        if not alive[i]:
            return False
        l, r = left[i], right[i]
        return (l < 0 or order_ids[i] > order_ids[l]) and (r >= n or order_ids[i] > order_ids[r])

    for i in range(n):
        if eligible(i):
            heappush(heap, (order_ids[i], i))

    result: list[int] = []
    while heap:
        value, i = heappop(heap)
        if not eligible(i):
            continue
        alive[i] = False
        result.append(value)
        l, r = left[i], right[i]
        if l >= 0:
            right[l] = r
        if r < n:
            left[r] = l
        for neighbor in (l, r):
            if 0 <= neighbor < n and eligible(neighbor):
                heappush(heap, (order_ids[neighbor], neighbor))
    if len(result) != n:
        raise RuntimeError("no eligible order despite remaining orders")
    return result

复杂度

初始化 O(n)，每次删除更新常数个邻居，但最小候选的堆插入/弹出为 O(log n)；最多 O(n) 次有效删除及 O(n) 个惰性候选，总时间 O(n log n)、空间 O(n)。只说邻居更新 O(1) 不能据此宣称全题 O(n)，因为还需选最小峰值。

易错点与追问

容易失分的边界

• 每轮全量扫描找峰值是 O(n²)；删除后非邻居的比较关系不变，才可局部更新。
• 用数组原地删除会让后续位置整体左移，平均 O(n)；left/right 保持原索引稳定。
• 旧堆项可能已经被删除，或随着邻居变化不再满足峰值；出堆时必须检查 alive 和当前邻接条件。
• 重复 ID 的严格大于与最小值平局规则没有在公开题面中定明，不应悄悄用 index 作为原题规则。

继续深挖

• 如果订单是流式插入，需定义插入位置与何时处理；双向链表能 O(1) 接入已知邻居，但全局最小仍需要堆或有序结构。
• 如果要求稳定处理相同数值，先问相等邻居能否成为峰值、平局按原始下标还是时间；确认后再调整比较与堆键。