1801. 积压订单中的订单总数

难度

• Easy
• Medium
• Hard

思路

只要读懂题目，明白流程，就能看出，我们需要频繁获取积压订单中的最大/最小价格，那么很容易想到大根堆小根堆，则问题迎刃而解。

因为 Python 中没有现成的大根堆，所以我们将价格取负放进堆中，间接成为大根堆。

每遇到一个买单，检查卖单堆，如果堆空，或者堆内最小元素大于买单价格，那么将买单插入买单堆中，否则需要循环取出卖单堆中的最小元素来与买单抵消。直到卖单堆中没有符合条件的元素，或者买单已经被抵消完。

遇到卖单也是同理。

最后将两个堆中的所有 amount 累加返回即可。

代码

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        sellHp = [] # 小根堆
        buyHp = [] # 大根堆
        for p, a, t in orders:
            if t == 0:
                if (not sellHp) or sellHp[0][0] > p:
                    heappush(buyHp, [-p, a])
                else:
                    while sellHp and a > 0 and sellHp[0][0] <= p:
                        sell = heappop(sellHp)
                        doneAm = sell[1] if sell[1] < a else a
                        sell[1] -= doneAm
                        a -= doneAm
                        if sell[1] > 0:
                            heappush(sellHp, sell)
                    if a > 0:
                        heappush(buyHp, [-p, a])
            else:
                if (not buyHp) or (-buyHp[0][0]) < p:
                    heappush(sellHp, [p, a])
                else:
                    while buyHp and a > 0 and (-buyHp[0][0]) >= p:
                        buy = heappop(buyHp)
                        doneAm = buy[1] if buy[1] < a else a
                        buy[1] -= doneAm
                        a -= doneAm
                        if buy[1] > 0:
                            heappush(buyHp, buy)
                    if a > 0:
                        heappush(sellHp, [p, a])
        sellNum = buyNum = 0
        for sell in sellHp:
            sellNum = (sellNum + sell[1]) % 1000000007
        for buy in buyHp:
            buyNum = (buyNum + buy[1]) % 1000000007
        return (sellNum + buyNum) % 1000000007