Medium
题目描述
给你一个二维整数数组 orders，其中每个 orders[i] = [pricei, amounti, orderTypei] 表示有 amounti 笔类型为 orderTypei、价格为 pricei 的订单。
订单类型 orderTypei 可以分为两种：
0表示这是一批采购订单 buy1表示这是一批销售订单 sell
注意，orders[i] 表示一批共 amounti 笔的独立订单，这些订单的价格和类型相同。对于所有有效的 i，由 orders[i] 表示的所有订单提交时间均早于 orders[i+1] 表示的所有订单。
存在一个由未执行订单组成的积压订单，积压订单最初是空的。提交订单时，会发生以下情况：
- 如果该订单是一笔采购订单，则查看积压订单中价格最低的销售订单。如果该销售订单的价格小于或等于当前采购订单的价格，则匹配并执行这些订单，并将销售订单从积压订单中删除。否则，采购订单将会添加到积压订单中。
- 反之亦然，如果该订单是一笔销售订单，则查看积压订单中价格最高的采购订单。如果该采购订单的价格大于或等于当前销售订单的价格，则匹配并执行这些订单，并将采购订单从积压订单中删除。否则，销售订单将会添加到积压订单中。
输入所有订单后，返回积压订单中的订单总数。由于数字可能很大，所以需要返回对 10^9 + 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 笔采购订单与价格最低（价格为 25）的 1 笔销售订单匹配，从积压订单中删除这 1 笔销售订单。积压订单中不再有销售订单，所以第 4 笔采购订单添加到积压订单中。
最终，积压订单中有 5 笔价格为 10 的采购订单，和 1 笔价格为 30 的采购订单。所以积压订单中的订单总数为 6 。
示例 2：
输入：orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
输出：999999984
提示：
1 <= orders.length <= 10^5orders[i].length == 31 <= pricei, amounti <= 10^9orderTypei为0或1
解题思路
这道题的核心是模拟订单匹配的过程，需要使用两个堆来维护积压订单：
思路分析：
数据结构选择：
- 采购订单（buy orders）：使用最大堆按价格排序，因为我们需要找到价格最高的采购订单来匹配销售订单
- 销售订单（sell orders）：使用最小堆按价格排序，因为我们需要找到价格最低的销售订单来匹配采购订单
订单匹配逻辑：
- 对于采购订单：找积压中价格最低的销售订单，如果销售价格 ≤ 采购价格，则匹配
- 对于销售订单：找积压中价格最高的采购订单，如果采购价格 ≥ 销售价格，则匹配
- 匹配时要处理数量，可能需要部分匹配
实现细节：
- 堆中存储
[价格, 数量]的配对 - 匹配过程中，如果一方订单完全匹配完，从堆中移除；如果部分匹配，更新剩余数量
- 最后统计所有积压订单的总数量，注意取模
- 堆中存储
优化考虑：
- 由于数据规模较大（10^9），需要使用
long long避免溢出 - 匹配过程要高效，堆操作的时间复杂度为 O(log n)
- 由于数据规模较大（10^9），需要使用
代码实现
class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
const int MOD = 1e9 + 7;
// 采购订单：最大堆（按价格）
priority_queue<pair<int, long long>> buyOrders;
// 销售订单：最小堆（按价格）
priority_queue<pair<int, long long>, vector<pair<int, long long>>, greater<pair<int, long long>>> sellOrders;
for (auto& order : orders) {
int price = order[0];
long long amount = order[1];
int type = order[2];
if (type == 0) { // 采购订单
while (amount > 0 && !sellOrders.empty() && sellOrders.top().first <= price) {
auto [sellPrice, sellAmount] = sellOrders.top();
sellOrders.pop();
long long matched = min(amount, sellAmount);
amount -= matched;
sellAmount -= matched;
if (sellAmount > 0) {
sellOrders.push({sellPrice, sellAmount});
}
}
if (amount > 0) {
buyOrders.push({price, amount});
}
} else { // 销售订单
while (amount > 0 && !buyOrders.empty() && buyOrders.top().first >= price) {
auto [buyPrice, buyAmount] = buyOrders.top();
buyOrders.pop();
long long matched = min(amount, buyAmount);
amount -= matched;
buyAmount -= matched;
if (buyAmount > 0) {
buyOrders.push({buyPrice, buyAmount});
}
}
if (amount > 0) {
sellOrders.push({price, amount});
}
}
}
long long result = 0;
while (!buyOrders.empty()) {
result = (result + buyOrders.top().second) % MOD;
buyOrders.pop();
}
while (!sellOrders.empty()) {
result = (result + sellOrders.top().second) % MOD;
sellOrders.pop();
}
return result;
}
};
class Solution:
def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
import heapq
MOD = 10**9 + 7
# 采购订单：最大堆（用负数实现）
buy_orders = [] # [(-price, amount)]
# 销售订单：最小堆
sell_orders = [] # [(price, amount)]
for price, amount, order_type in orders:
if order_type == 0: # 采购订单
while amount > 0 and sell_orders and sell_orders[0][0] <= price:
sell_price, sell_amount = heapq.heappop(sell_orders)
matched = min(amount, sell_amount)
amount -= matched
sell_amount -= matched
if sell_amount > 0:
heapq.heappush(sell_orders, (sell_price, sell_amount))
if amount > 0:
heapq.heappush(buy_orders, (-price, amount))
else: # 销售订单
while amount > 0 and buy_orders and -buy_orders[0][0] >= price:
neg_buy_price, buy_amount = heapq.heappop(buy_orders)
matched = min(amount, buy_amount)
amount -= matched
buy_amount -= matched
if buy_amount > 0:
heapq.heappush(buy_orders, (neg_buy_price, buy_amount))
if amount > 0:
heapq.heappush(sell_orders, (price, amount))
result = 0
for _, amount in buy_orders:
result = (result + amount) % MOD
for _, amount in sell_orders:
result = (result + amount) % MOD
return result
public class Solution {
public int GetNumberOfBacklogOrders(int[][] orders) {
const int MOD = 1000000007;
// 采购订单：最大堆
var buyOrders = new PriorityQueue<(int price, long amount), int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
// 销售订单：最小堆
var sellOrders = new PriorityQueue<(int price, long amount), int>();
foreach (var order in orders) {
int price = order[0];
long amount = order[1];
int type = order[2];
if (type == 0) { // 采购订单
while (amount > 0 && sellOrders.Count > 0) {
var (sellPrice, sellAmount) = sellOrders.Peek();
if (sellPrice > price) break;
sellOrders.Dequeue();
long matched = Math.Min(amount, sellAmount);
amount -= matched;
sellAmount -= matched;
if (sellAmount > 0) {
sellOrders.Enqueue((sellPrice, sellAmount), sellPrice);
}
}
if (amount > 0) {
buyOrders.Enqueue((price, amount), price);
}
} else { // 销售订单
while (amount > 0 && buyOrders.Count > 0) {
var (buyPrice, buyAmount) = buyOrders.Peek();
if (buyPrice < price) break;
buyOrders.Dequeue();
long matched = Math.Min(amount, buyAmount);
amount -= matched;
buyAmount -= matched;
if (buyAmount > 0) {
buyOrders.Enqueue((buyPrice, buyAmount), buyPrice);
}
}
if (amount > 0) {
sellOrders.Enqueue((price, amount), price);
}
}
}
long result = 0;
while (buyOrders.Count > 0) {
result = (result + buyOrders.Dequeue().amount) % MOD;
}
while (sellOrders.Count > 0) {
result = (result + sellOrders.Dequeue().amount) % MOD;
}
return (int)result;
}
}
var getNumberOfBacklogOrders = function(orders) {
const buyOrders = new MaxPriorityQueue({ priority: (x) => x[0] });
const sellOrders = new MinPriorityQueue({ priority: (x) => x[0] });
for (let [price, amount, type] of orders) {
if (type === 0) { // buy order
while (amount > 0 && !sellOrders.isEmpty() && sellOrders.front().element[0] <= price) {
const [sellPrice, sellAmount] = sellOrders.dequeue().element;
const matched = Math.min(amount, sellAmount);
amount -= matched;
if (sellAmount > matched) {
sellOrders.enqueue([sellPrice, sellAmount - matched]);
}
}
if (amount > 0) {
buyOrders.enqueue([price, amount]);
}
} else { // sell order
while (amount > 0 && !buyOrders.isEmpty() && buyOrders.front().element[0] >= price) {
const [buyPrice, buyAmount] = buyOrders.dequeue().element;
const matched = Math.min(amount, buyAmount);
amount -= matched;
if (buyAmount > matched) {
buyOrders.enqueue([buyPrice, buyAmount - matched]);
}
}
if (amount > 0) {
sellOrders.enqueue([price, amount]);
}
}
}
let total = 0;
const MOD = 1000000007;
while (!buyOrders.isEmpty()) {
total = (total + buyOrders.dequeue().element[1]) % MOD;
}
while (!sellOrders.isEmpty()) {
total = (total + sellOrders.dequeue().element[1]) % MOD;
}
return total;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |