题目

给你一个二维整数数组 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 取余的结果。

解题思路

这题就是一个读题题，就是将订单加入优先队列，然后两个优先队列对冲。

我用Python写了一个完整的大根堆和小根堆

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
class Solution:
    # 大根堆下滤
    def siftdownMax(self, heap: list, startpos, pos):
        # 要添加的元素
        newitem = heap[pos]
        while pos > startpos:
            # 父节点下标
            parentpos = (pos - 1) >> 1
            # 父节点值
            parent = heap[parentpos]
            # 父节点值小于新值，节点要下移，同时新值要上移
            if parent <= newitem:
                heap[pos] = heap[parentpos]
                pos = parentpos
                continue
            break
        heap[pos] = newitem


    # 大根堆上滤
    def siftupMax(self, heap, pos):
        endpos = len(heap)
        startpos = pos
        newitem = heap[pos]
        # 左孩子下标
        childpos = pos * 2 + 1
        while childpos < endpos:
            # 右孩子下标
            rightpos = childpos + 1
            # 左右孩子取值最大的
            if rightpos < endpos and heap[rightpos] > heap[childpos]:
                childpos = rightpos
            heap[pos] = heap[childpos]
            pos = childpos
            childpos = pos * 2 + 1
        heap[pos] = newitem
        # 调整父节点
        self.siftdownMax(heap, startpos, pos)


    # 小根堆下滤
    def siftdownMin(self, heap: list, startpos, pos):
        # 要添加的元素
        newitem = heap[pos]
        while pos > startpos:
            # 父节点下标
            parentpos = (pos - 1) >> 1
            # 父节点值
            parent = heap[parentpos]
            # 父节点值大于新值，节点要下移，同时新值要上移
            if parent >= newitem:
                heap[pos] = heap[parentpos]
                pos = parentpos
                continue
            break
        heap[pos] = newitem


    # 小根堆上滤
    def siftupMin(self, heap, pos):
        endpos = len(heap)
        startpos = pos
        newitem = heap[pos]
        # 左孩子下标
        childpos = pos * 2 + 1
        while childpos < endpos:
            # 右孩子下标
            rightpos = childpos + 1
            # 左右孩子取值最小的
            if rightpos < endpos and heap[rightpos] < heap[childpos]:
                childpos = rightpos
            heap[pos] = heap[childpos]
            pos = childpos
            childpos = pos * 2 + 1
        heap[pos] = newitem
        # 调整父节点
        self.siftdownMin(heap, startpos, pos)

    # 大根堆入队
    def heappushMax(self, heap: list, item):
        heap.append(item)
        # 堆顶是列表的尾巴heap[-1]，堆底部是列表的头heap[0]
        self.siftdownMax(heap, 0, len(heap) - 1)


    # 大根堆弹出
    def heappopMax(self, heap):
        lastitem = heap.pop()
        if heap:
            # 获取要弹出的元素
            returnitem = heap[0]
            # 堆底放到堆顶
            heap[0] = lastitem
            # 堆顶元素下滤
            self.siftupMax(heap, 0)
            # 返回弹出的元素
            return returnitem
        return lastitem

    # 小根堆入队
    def heappushMin(self, heap: list, item):
        heap.append(item)
        # 堆顶是列表的尾巴heap[-1]，堆底部是列表的头heap[0]
        self.siftdownMin(heap, 0, len(heap) - 1)


    # 小根堆弹出
    def heappopMin(self, heap):
        lastitem = heap.pop()
        if heap:
            # 获取要弹出的元素
            returnitem = heap[0]
            # 堆底放到堆顶
            heap[0] = lastitem
            # 堆顶元素下滤
            self.siftupMin(heap, 0)
            # 返回弹出的元素
            return returnitem
        return lastitem


    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        ans = 0

        def deleteOrder():
            nonlocal ans
            if buyOrder and sellOrder:
                buyPrice, sellPrice = buyOrder[0], sellOrder[0]
                while buyOrder and sellOrder and buyPrice >= sellPrice:
                    if buy[buyPrice] > sell[sellPrice]:
                        ans -= sell[sellPrice] * 2
                        buy[buyPrice] -= sell[sellPrice]
                        sell.pop(sellPrice)
                        self.heappopMin(sellOrder)
                    elif buy[buyPrice] < sell[sellPrice]:
                        ans -= buy[buyPrice] * 2
                        sell[sellPrice] -= buy[buyPrice]
                        buy.pop(buyPrice)
                        self.heappopMax(buyOrder)
                    else:
                        ans -= buy[buyPrice] + sell[sellPrice]
                        buy.pop(buyPrice)
                        sell.pop(sellPrice)
                        self.heappopMin(sellOrder)
                        self.heappopMax(buyOrder)
                    if buyOrder and sellOrder:
                        buyPrice, sellPrice = buyOrder[0], sellOrder[0]
        

        # 初始化
        buyOrder, sellOrder = [], []  # 优先队列  buy:大根堆 sell:小根堆
        buy, sell = defaultdict(int), defaultdict(int)  # 哈希表

        for price, amount, orderType in orders:
            if orderType == 0:
                ans += amount
                buy[price] += amount
                self.heappushMax(buyOrder, price)
                deleteOrder()
            else:
                ans += amount
                sell[price] += amount
                self.heappushMin(sellOrder, price)
                deleteOrder()
        return ans % MOD

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        using pii = pair<int, int>;
        priority_queue<pii, vector<pii>, greater<pii>> sell;
        priority_queue<pii> buy;
        for (auto& e : orders) {
            int p = e[0], a = e[1], t = e[2];
            if (t == 0) {
                while (a && !sell.empty() && sell.top().first <= p) {
                    auto [x, y] = sell.top();
                    sell.pop();
                    if (a >= y) {
                        a -= y;
                    } else {
                        sell.push({x, y - a});
                        a = 0;
                    }
                }
                if (a) {
                    buy.push({p, a});
                }
            } else {
                while (a && !buy.empty() && buy.top().first >= p) {
                    auto [x, y] = buy.top();
                    buy.pop();
                    if (a >= y) {
                        a -= y;
                    } else {
                        buy.push({x, y - a});
                        a = 0;
                    }
                }
                if (a) {
                    sell.push({p, a});
                }
            }
        }
        long ans = 0;
        while (!buy.empty()) {
            ans += buy.top().second;
            buy.pop();
        }
        while (!sell.empty()) {
            ans += sell.top().second;
            sell.pop();
        }
        const int mod = 1e9 + 7;
        return ans % mod;
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func getNumberOfBacklogOrders(orders [][]int) (ans int) {
	sell := hp{}
	buy := hp{}
	for _, e := range orders {
		p, a, t := e[0], e[1], e[2]
		if t == 0 {
			for a > 0 && len(sell) > 0 && sell[0].p <= p {
				q := heap.Pop(&sell).(pair)
				x, y := q.p, q.a
				if a >= y {
					a -= y
				} else {
					heap.Push(&sell, pair{x, y - a})
					a = 0
				}
			}
			if a > 0 {
				heap.Push(&buy, pair{-p, a})
			}
		} else {
			for a > 0 && len(buy) > 0 && -buy[0].p >= p {
				q := heap.Pop(&buy).(pair)
				x, y := q.p, q.a
				if a >= y {
					a -= y
				} else {
					heap.Push(&buy, pair{x, y - a})
					a = 0
				}
			}
			if a > 0 {
				heap.Push(&sell, pair{p, a})
			}
		}
	}
	const mod int = 1e9 + 7
	for len(buy) > 0 {
		ans += heap.Pop(&buy).(pair).a
	}
	for len(sell) > 0 {
		ans += heap.Pop(&sell).(pair).a
	}
	return ans % mod
}

type pair struct{ p, a int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].p < h[j].p }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }