积压订单中的订单总数

标签: 数组 模拟 堆（优先队列）

难度: Medium

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

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

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

注意，orders[i] 表示一批共计 amounti 笔的独立订单，这些订单的价格和类型相同。对于所有有效的 i ，由 orders[i] 表示的所有订单提交时间均早于 orders[i+1] 表示的所有订单。

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

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

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

 

示例 1：

输入：orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
输出：6
解释：输入订单后会发生下述情况：
- 提交 5 笔采购订单，价格为 10 。没有销售订单，所以这 5 笔订单添加到积压订单中。
- 提交 2 笔销售订单，价格为 15 。没有采购订单的价格大于或等于 15 ，所以这 2 笔订单添加到积压订单中。
- 提交 1 笔销售订单，价格为 25 。没有采购订单的价格大于或等于 25 ，所以这 1 笔订单添加到积压订单中。
- 提交 4 笔采购订单，价格为 30 。前 2 笔采购订单与价格最低（价格为 15）的 2 笔销售订单匹配，从积压订单中删除这 2 笔销售订单。第 3 笔采购订单与价格最低的 1 笔销售订单匹配，销售订单价格为 25 ，从积压订单中删除这 1 笔销售订单。积压订单中不存在更多销售订单，所以第 4 笔采购订单需要添加到积压订单中。
最终，积压订单中有 5 笔价格为 10 的采购订单，和 1 笔价格为 30 的采购订单。所以积压订单中的订单总数为 6 。

示例 2：

输入：orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
输出：999999984
解释：输入订单后会发生下述情况：
- 提交 109 笔销售订单，价格为 7 。没有采购订单，所以这 109 笔订单添加到积压订单中。
- 提交 3 笔采购订单，价格为 15 。这些采购订单与价格最低（价格为 7 ）的 3 笔销售订单匹配，从积压订单中删除这 3 笔销售订单。
- 提交 999999995 笔采购订单，价格为 5 。销售订单的最低价为 7 ，所以这 999999995 笔订单添加到积压订单中。
- 提交 1 笔销售订单，价格为 5 。这笔销售订单与价格最高（价格为 5 ）的 1 笔采购订单匹配，从积压订单中删除这 1 笔采购订单。
最终，积压订单中有 (1000000000-3) 笔价格为 7 的销售订单，和 (999999995-1) 笔价格为 5 的采购订单。所以积压订单中的订单总数为 1999999991 ，等于 999999984 % (109 + 7) 。

 

提示：

  • 1 <= orders.length <= 105
  • orders[i].length == 3
  • 1 <= pricei, amounti <= 109
  • orderTypei 为 0 或 1

Submission

运行时间: 105 ms

内存: 47.5 MB

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buys = list()
        heapify(buys)
        sells = list()
        heapify(sells)
        for p, a, t in orders:
            if t == 0:
                while a and sells and p >= sells[0][0]:
                    val = sells[0][1]
                    if val <= a:
                        heappop(sells)
                        a -= val
                    else:
                        sells[0][1] -= a
                        a = 0
                if a:
                    heappush(buys, [-p, a])
            else:
                while a and buys and p <= -buys[0][0]:
                    val = buys[0][1]
                    if val <= a:
                        heappop(buys)
                        a -= val
                    else:
                        buys[0][1] -= a
                        a = 0
                if a:
                    heappush(sells, [p, a])
        ans = 0
        for b in buys:
            ans += b[1]
        for s in sells:
            ans += s[1]
        return ans % (10 ** 9 + 7)

Explain

该题解采用两个最小堆（min-heaps）来处理积压订单，一个堆（buys）用于处理采购订单，而另一个堆（sells）用于处理销售订单。buys堆中存储负的价格值以模拟最大堆的行为，使得价格最高的采购订单总是在堆顶。处理订单时，根据订单类型，检查是否可以与堆顶的订单匹配和执行。如果不能匹配，将订单加入相应的堆中。最后，遍历两个堆，累加剩余订单的数量，返回这个总数对1,000,000,007取模的结果。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buys = []  # 用于存储采购订单，价格取负值以模拟最大堆
        heapify(buys)
        sells = []  # 用于存储销售订单
        heapify(sells)
        for p, a, t in orders:
            if t == 0:  # 处理采购订单
                while a and sells and p >= sells[0][0]:
                    val = sells[0][1]
                    if val <= a:
                        heappop(sells)  # 销售订单完全被采购
                        a -= val
                    else:
                        sells[0][1] -= a  # 部分销售订单被采购
                        a = 0
                if a:
                    heappush(buys, [-p, a])  # 未完全匹配的采购订单加入堆
            else:  # 处理销售订单
                while a and buys and p <= -buys[0][0]:
                    val = buys[0][1]
                    if val <= a:
                        heappop(buys)  # 采购订单完全被销售
                        a -= val
                    else:
                        buys[0][1] -= a  # 部分采购订单被销售
                        a = 0
                if a:
                    heappush(sells, [p, a])  # 未完全匹配的销售订单加入堆
        ans = sum(b[1] for b in buys) + sum(s[1] for s in sells)  # 计算所有堆中订单的总数
        return ans % (10 ** 9 + 7)  # 返回结果对1,000,000,007取模

Explore

在处理采购订单时，优先检查价格最低的销售订单是为了确保采购者可以以最低的成本购买商品。这种做法基于市场机制的'买方希望以最低价格购买'的原则。此策略确保了从经济角度看，采购订单可以尽可能节约成本，同时促进市场上订单的有效匹配和快速执行。如果反向操作，即用较高价格销售给采购订单，可能会导致不必要的高成本交易，且不符合市场的自然交易行为。因此，这种方法是优化订单执行的最优策略。

使用最小堆来模拟最大堆通过取负值是一种常见的技巧，但它有几个潜在的风险或限制。首先，这种方法要求所有涉及的数值操作必须考虑到符号变换，这增加了编码的复杂性和出错的可能性。其次，如果原始数据中包含极限值，比如整数类型的最小值（如Python中的int类型），取负可能会导致溢出错误。此外，这种转换对于阅读和理解代码的人来说可能不直观，增加了代码的维护难度。

如果大量订单价格相同，堆的处理效率可能会受到影响，因为堆结构是基于元素之间的比较来维护其性质。在极端情况下，相同价格的订单可能导致堆操作（如插入和删除）的效率下降，因为堆需要通过额外的比较来确定元素的准确位置。一种可能的解决方案是在堆中使用一个二级标准（如时间戳或订单ID）来保持元素的一致排序，这样即使价格相同，堆也可以根据次要标准快速决定元素的位置，从而优化性能。

在实际实现中，确实需要考虑整数溢出的问题，尤其是在处理大数据量时。题解中通过对最终结果取模1,000,000,007（一个大质数），有效地防止了整数溢出。在Python中，int类型可以自动处理大整数，但在一些其他编程语言中可能需要显式处理这种情况。取模操作不仅可以避免溢出，还可以保持数字在一个可管理的范围内，从而确保计算结果的准确性和可靠性。