算法

大顶堆存买单堆buy(买盘)，小顶堆存卖单堆sell(卖盘)；

每次有新的买单，就从卖单堆顶部开始相互抵消（买单价格需要高于最小卖单，不断循环直到无法交易），
如果抵消后买单还有剩余，就存入买单堆。

有新的卖单思路一样。

最后统计一下剩余单子数量即可。

(堆)

时间复杂度

$O(nlogn)$

C++ 代码

#define II pair<long long, long long> //订单价格、订单数量

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        int MOD = 1e9 + 7;
        priority_queue<II> buy; // 买盘 - 大顶堆
        priority_queue<II, vector<II>, greater<II>> sell;  // 卖盘 - 小顶堆
        int n = orders.size();
        for(auto x : orders) {
            if(!x[2]) { // 买单
                while(x[1] > 0 && sell.size() && x[0] >= sell.top().first) {
                    if(x[1] >= sell.top().second) {//买单可以吃下卖单堆顶部这个单子的数量
                        x[1] -= sell.top().second;
                        sell.pop();
                    } else { //买单不足以吃下卖单堆顶部这个单子的数量，则买单数归零，消耗一部分堆顶
                        auto t = sell.top();
                        sell.pop();
                        t.second -= x[1];
                        sell.push(t);
                        x[1] = 0;
                    }
                }
                if(x[1]) buy.push({x[0], x[1]});//若买单还有剩余，则剩余部分存入买单堆
            } else { //卖单
                while(x[1] > 0 && buy.size() && x[0] <= buy.top().first) {
                    if(x[1] >= buy.top().second) {
                        x[1] -= buy.top().second;
                        buy.pop();
                    } else {
                        auto t = buy.top();
                        buy.pop();
                        t.second -= x[1];
                        buy.push(t);
                        x[1] = 0;
                    }
                }
                if(x[1]) sell.push({x[0], x[1]});
            }
        }
        //统计剩余单子数量
        long long cnt = 0;
        while (buy.size()) cnt += buy.top().second, buy.pop();
        while (sell.size()) cnt += sell.top().second, sell.pop();
        return cnt % MOD;
    }
};