1801.积压订单中的订单总数
链接：1801.积压订单中的订单总数
难度：Medium
标签：数组、模拟、堆（优先队列）
简介：给你一个二维整数数组 orders ，输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对 109 + 7 取余的结果。
题解 1 - typescript
- 编辑时间：2021-04-11
- 执行用时：332ms
- 内存消耗：59.5MB
- 编程语言：typescript
- 解法介绍：利用买大顶堆和卖小顶堆维护最值。
class Heap<T = number> {
private arr: T[] = [];
get isEmpty() {
return this.size === 0;
}
get size() {
return this.arr.length;
}
get top() {
return this.arr[0];
}
constructor(private compare: (t1: T, t2: T) => number) {}
add(num: T): void {
this.arr.push(num);
this.shiftUp(this.size - 1);
}
remove(): T {
const num = this.arr.shift()!;
if (this.size) {
this.arr.unshift(this.arr.pop()!);
this.shiftDown(0);
}
return num;
}
private shiftUp(index: number): void {
if (index === 0) return;
const parentIndex = (index - 1) >> 1;
if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
[this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
this.shiftUp(parentIndex);
}
}
private shiftDown(index: number): void {
let childrenIndex = index * 2 + 1;
if (childrenIndex > this.size - 1) return;
if (
childrenIndex + 1 <= this.size - 1 &&
this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
) {
childrenIndex++;
}
if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
[this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
this.shiftDown(childrenIndex);
}
}
*[Symbol.iterator](): IterableIterator<T> {
for (const t of this.arr) {
yield t;
}
}
}
function getNumberOfBacklogOrders(orders: number[][]): number {
const buyHeap = new Heap<number[]>(([t1], [t2]) => t1 - t2);
const sellHeap = new Heap<number[]>(([t1], [t2]) => t2 - t1);
const add = (order: number[]) => {
(order[2] === 0 ? buyHeap : sellHeap).add(order);
while (buyHeap.size > 0 && sellHeap.size > 0 && buyHeap.top[0] >= sellHeap.top[0]) {
const buyTop = buyHeap.top;
const sellTop = sellHeap.top;
if (buyTop[1] > sellTop[1]) {
sellHeap.remove();
buyTop[1] -= sellTop[1];
} else if (buyTop[1] < sellTop[1]) {
buyHeap.remove();
sellTop[1] -= buyTop[1];
} else {
sellHeap.remove();
buyHeap.remove();
}
}
};
orders.forEach(order => add(order));
let ans = 0;
for (const [, c] of buyHeap) ans += c;
for (const [, c] of sellHeap) ans += c;
return ans % (10 ** 9 + 7);
}
题解 2 - cpp
- 编辑时间：2023-01-02
- 执行用时：188ms
- 内存消耗：57.2MB
- 编程语言：cpp
- 解法介绍：模拟。
typedef pair<int, int> node;
#define X first
#define Y second
struct cmp {
int type;
cmp(int type): type(type) {}
bool operator()(node &a, node &b) {
if (type) return a.X < b.X;
else return a.X > b.X;
}
};
int mod = 1e9 + 7;
class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
priority_queue<node, vector<node>, cmp> buyq(cmp(1));
priority_queue<node, vector<node>, cmp> sellq(cmp(0));
for (auto &order : orders) {
if (order[2] == 0) {
node cur = make_pair(order[0], order[1]);
while (cur.Y && sellq.size() && sellq.top().X <= cur.X) {
if (sellq.top().Y > cur.Y) {
auto v = sellq.top();
sellq.pop();
v.Y -= cur.Y;
sellq.push(v);
cur.Y = 0;
} else if (sellq.top().Y < cur.Y) {
cur.Y -= sellq.top().Y;
sellq.pop();
} else {
cur.Y = 0;
sellq.pop();
}
}
if (cur.Y) buyq.push(cur);
} else {
node cur = make_pair(order[0], order[1]);
while (cur.Y && buyq.size() && buyq.top().X >= cur.X) {
if (buyq.top().Y > cur.Y) {
auto v = buyq.top();
buyq.pop();
v.Y -= cur.Y;
buyq.push(v);
cur.Y = 0;
} else if (buyq.top().Y < cur.Y) {
cur.Y -= buyq.top().Y;
buyq.pop();
} else {
cur.Y = 0;
buyq.pop();
}
}
if (cur.Y) sellq.push(cur);
}
}
int ans = 0;
while (buyq.size()) ans = (ans + buyq.top().Y) % mod, buyq.pop();
while (sellq.size()) ans = (ans + sellq.top().Y) % mod, sellq.pop();
return ans;
}
};
题解 3 - cpp
- 编辑时间：2023-01-02
- 执行用时：200ms
- 内存消耗：57.2MB
- 编程语言：cpp
- 解法介绍：同上。
typedef pair<int, int> node;
#define X first
#define Y second
struct cmp {
int type;
cmp(int type): type(type) {}
bool operator()(node &a, node &b) {
if (type) return a.X < b.X;
else return a.X > b.X;
}
};
int mod = 1e9 + 7;
class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
priority_queue<node, vector<node>, cmp> buyq(cmp(1));
priority_queue<node, vector<node>, cmp> sellq(cmp(0));
for (auto &order : orders) {
auto &q1 = order[2] == 0 ? sellq : buyq,
&q2 = order[2] == 0 ? buyq : sellq;
node cur = make_pair(order[0], order[1]);
while (cur.Y && q1.size() && (order[2] == 0 ? q1.top().X <= cur.X : q1.top().X >= cur.X)) {
if (q1.top().Y > cur.Y) {
auto v = q1.top();
q1.pop();
v.Y -= cur.Y;
q1.push(v);
cur.Y = 0;
} else if (q1.top().Y < cur.Y) {
cur.Y -= q1.top().Y;
q1.pop();
} else {
cur.Y = 0;
q1.pop();
}
}
if (cur.Y) q2.push(cur);/
}
int ans = 0;
while (buyq.size()) ans = (ans + buyq.top().Y) % mod, buyq.pop();
while (sellq.size()) ans = (ans + sellq.top().Y) % mod, sellq.pop();
return ans;
}
};
题解 4 - rust
- 编辑时间：2023-01-02
- 执行用时：24ms
- 内存消耗：9.5MB
- 编程语言：rust
- 解法介绍：同上。
use std::{cmp::Ordering, collections::BinaryHeap};
struct Node(i32, i32, bool);
impl PartialEq for Node {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0
}
}
impl Eq for Node {}
impl Ord for Node {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
if self.2 {
self.0.cmp(&other.0)
} else {
other.0.cmp(&self.0)
}
}
}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
if self.2 {
self.0.partial_cmp(&other.0)
} else {
other.0.partial_cmp(&self.0)
}
}
}
const mode: i32 = 1000000000 + 7;
impl Solution {
pub fn get_number_of_backlog_orders(orders: Vec<Vec<i32>>) -> i32 {
let mut buy_heap = BinaryHeap::<Node>::new();
let mut sell_heap = BinaryHeap::<Node>::new();
for order in orders {
if order[2] == 0 {
let mut cur = Node(order[0], order[1], order[2] == 0);
while cur.1 > 0 && !buy_heap.is_empty() && buy_heap.peek().unwrap().0 <= cur.0 {
if buy_heap.peek().unwrap().1 > cur.1 {
let mut node = buy_heap.pop().unwrap();
node.1 -= cur.1;
buy_heap.push(node);
cur.1 = 0;
} else if buy_heap.peek().unwrap().1 < cur.1 {
cur.1 -= buy_heap.pop().unwrap().1;
} else {
cur.1 = 0;
buy_heap.pop();
}
}
if cur.1 > 0 {
sell_heap.push(cur);
};
} else {
let mut cur = Node(order[0], order[1], order[2] == 0);
while cur.1 > 0 && !sell_heap.is_empty() && sell_heap.peek().unwrap().0 >= cur.0 {
if sell_heap.peek().unwrap().1 > cur.1 {
let mut node = sell_heap.pop().unwrap();
node.1 -= cur.1;
sell_heap.push(node);
cur.1 = 0;
} else if sell_heap.peek().unwrap().1 < cur.1 {
cur.1 -= sell_heap.pop().unwrap().1;
} else {
cur.1 = 0;
sell_heap.pop();
}
}
if cur.1 > 0 {
buy_heap.push(cur);
};
}
}
let mut ans = 0;
while !buy_heap.is_empty() {
ans = (ans + buy_heap.pop().unwrap().1) % mode;
}
while !sell_heap.is_empty() {
ans = (ans + sell_heap.pop().unwrap().1) % mode;
}
ans
}
}