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

类型：堆

• 1801. 积压订单中的订单总数 💛 ⭐

  https://leetcode-cn.com/problems/number-of-orders-in-the-backlog/

  ❓ 给你一个二维整数数组 orders ，其中每个 orders[i] = [price, amount, orderType] 表示有 amount 笔类型为 orderType、价格为 price 的订单。

  订单类型 orderTypei 可以分为两种：

  • 0 表示这是一批采购订单 buy
  • 1 表示这是一批销售订单 sell

  存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时，会发生以下情况：

  • 如果该订单是一笔采购订单 buy ，则可以查看积压订单中价格 最低 的销售订单 sell 。如果该销售订单 sell 的价格 低于或等于 当前采购订单 buy 的价格，则匹配并执行这两笔订单，并将销售订单 sell 从积压订单中删除。否则，采购订单 buy 将会添加到积压订单中。
  • 反之亦然，如果该订单是一笔销售订单 sell ，则可以查看积压订单中价格 最高 的采购订单 buy 。如果该采购订单 buy 的价格 高于或等于 当前销售订单 sell 的价格，则匹配并执行这两笔订单，并将采购订单 buy 从积压订单中删除。否则，销售订单 sell 将会添加到积压订单中。

  输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对 109 + 7 取余的结果。

  💡 堆

  我们用一个小顶堆来存储 sell 订单，用一个大顶堆来存储 buy 订单。

  class Solution:
      def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
          sellHeap = [] # 小顶堆
          buyHeap = [] # 大顶堆
          orderNum = 0
          max_num = 10 ** 9 + 7
  
          for [price, amount, orderType] in orders:
              # 先入堆
              if orderType == 0:
                  heapq.heappush(buyHeap, [-price, amount])
              else:
                  heapq.heappush(sellHeap, [price, amount])
              orderNum += amount
  
              while buyHeap and sellHeap and -buyHeap[0][0] >= sellHeap[0][0]:
                  sellAmount = sellHeap[0][1]
                  buyAmount = buyHeap[0][1]
                  minAmount = min(sellAmount, buyAmount)
                  orderNum -= 2 * minAmount
  
                  if sellAmount - minAmount > 0:
                      sellHeap[0][1] -= minAmount
                  else:
                      heapq.heappop(sellHeap)
  
                  if buyAmount - minAmount > 0:
                      buyHeap[0][1] -= minAmount
                  else:
                      heapq.heappop(buyHeap)
  
          return orderNum % max_num