共计 3509 个字符,预计需要花费 9 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 1801. 积压订单中的订单总数 ,难度为 中等。
Tag :「数据结构」、「模仿」、「优先队列(堆)」
给你一个二维整数数组 $orders$,其中每个 $orders[i] = [price_i, amount_i, orderType_i]$ 示意有 $amount_i$ 笔类型为 $orderType_i$、价格为 $price_i$ 的订单。
订单类型 $orderType_i = 0$ 示意这是一批洽购订单,$orderType_i = 1$ 示意这是一批销售订单。
留神,$orders[i]$ 示意一批共计 $amount_i$ 笔的独立订单,这些订单的价格和类型雷同。
对于所有无效的 $i$,由 $orders[i]$ 示意的所有订单提交工夫均早于 $orders[i+1]$ 示意的所有订单。
存在由未执行订单组成的积压订单。积压订单最后是空的。
提交订单时,会产生以下状况:
- 如果该订单是一洽购订单
buy
,则能够查看积压订单中价格 最低 的销售订单sell
。如果该销售订单sell
的价格 低于或等于 以后洽购订单buy
的价格,则匹配并执行这两笔订单,并将销售订单sell
从积压订单中删除。否则,洽购订单buy
将会增加到积压订单中。 - 如果该订单是一笔销售订单
sell
,则能够查看积压订单中价格 最高 的洽购订单buy
。如果该洽购订单buy
的价格 高于或等于 以后销售订单sell
的价格,则匹配并执行这两笔订单,并将洽购订单buy
从积压订单中删除。否则,销售订单sell
将会增加到积压订单中。
输出所有订单后,返回积压订单中的订单总数。
因为数字可能很大,所以须要返回对 $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 笔洽购订单与价格最低的 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 <= 10^5$
- $orders[i].length == 3$
- $1 <= pricei, amounti <= 10^9$
orderTypei
为 $0$ 或 $1$
模仿 + 数据结构
整顿题意:从前往后解决所有的 $orders[i]$,对于 buy
类型的订单,从积压订单中找价格低于等于以后价格的 sell
订单进行对消;同理,对于 sell
类型的订单,从积压订单中找价格高于等于以后价格的 buy
订单进行对消。问最终有多少积压订单。
这个找「最低 / 最高」价格的操作能够利用优先队列(堆)来做,对于积压的 buy
类型订单,咱们总是要找价格高的,应用大根堆保护;对于积压的 sell
类型订单,咱们总是要找价格低的,应用小根堆保护。
两个优先队列(堆)均保护形如 $(price_i, amount_i)$ 的二元组信息,代表价格为 $price_i$ 的订单积压了 $amount_i$ 单。
当解决(尝试匹配)了所有的 $orders[i]$ 之后,统计两个优先队列(堆)中订单数量即是答案。
Java 代码:
class Solution {public int getNumberOfBacklogOrders(int[][] orders) {PriorityQueue<int[]> buy = new PriorityQueue<>((a,b)->b[0]-a[0]), sell = new PriorityQueue<>((a,b)->a[0]-b[0]);
PriorityQueue<int[]> from = null, to = null;
boolean fromIsSell = false;
for (int[] order : orders) {int p = order[0], a = order[1], t = order[2];
if (t == 0) {from = sell; to = buy; fromIsSell = true;} else {from = buy; to = sell; fromIsSell = false;}
while (a > 0 && !from.isEmpty() && (fromIsSell ? from.peek()[0] <= p : from.peek()[0] >= p)) {int[] cur = from.poll();
int cnt = Math.min(cur[1], a);
cur[1] -= cnt; a -= cnt;
if (cur[1] > 0) from.add(cur);
}
if (a > 0) to.add(new int[]{p, a});
}
int ans = 0;
for (PriorityQueue<int[]> q : new PriorityQueue[]{buy, sell}) {while (!q.isEmpty()) {ans += q.poll()[1];
ans %= (int)1e9+7;
}
}
return ans;
}
}
Python 代码:
class Solution:
def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
buy, sell = [], []
for p, a, t in orders:
if t == 0:
from_heap, to_heap, from_is_sell = sell, buy, True
else:
from_heap, to_heap, from_is_sell = buy, sell, False
while a and from_heap and (from_heap[0][0] <= p if from_is_sell else -from_heap[0][0] >= p):
cur = heapq.heappop(from_heap)
if cur[1] > a:
heapq.heappush(from_heap, (cur[0], cur[1] - a))
a = 0
else:
a -= cur[1]
if a:
heapq.heappush(to_heap, (-p if from_is_sell else p, a))
ans, mod = 0, int(1e9)+7
for _, a in buy + sell:
ans += a
return ans % mod
- 工夫复杂度:令 $n$ 为数组
orders
的长度,复杂度为 $O(n\log{n})$ - 空间复杂度:$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1801
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布