题目描述

blablabla

样例

blablabla

写法

/*
    堆

    使用大根堆维护当前积压的买单，使用小跟堆维护当前积压的卖单。

    时间复杂度：O(nlogn)
    空间复杂度：O(n)
*/
const int N = 1e9 + 7;

class Solution {
public:
    struct buyOrders {
        int price, amount, orderType;
        bool operator< (const buyOrders& t) const {
            return price < t.price;
        }
    };

    struct sellOrders {
        int price, amount, orderType;
        bool operator< (const sellOrders& t) const {
            return price > t.price;
        }
    };

    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        priority_queue<buyOrders> buyHeap; // price 从大到小排序，找 max
        priority_queue<sellOrders> sellHeap; // price 从小到大排序，找 min

        for (auto& o : orders) {
            int price = o[0], amount = o[1], orderType = o[2];
            // cout << price << ", " << amount << ", " << orderType << endl;

            if (orderType == 0) { // buy
                while (sellHeap.size()) {
                    sellOrders t = sellHeap.top();
                    if (price >= t.price) {
                        if (amount >= t.amount) {
                            amount -= t.amount;
                            sellHeap.pop();
                        } else if (amount < t.amount) {
                            t.amount -= amount;
                            amount = 0;
                            sellHeap.pop();
                            sellHeap.push({t.price, t.amount, t.orderType});
                            break;
                        }
                    }
                    else if (price < t.price) break;
                }
                if (amount != 0) {
                    buyHeap.push({price, amount, orderType});
                }
            } else if (orderType == 1) { // sell
                while (buyHeap.size()) {
                    buyOrders t = buyHeap.top();
                    if (price <= t.price) {
                        if (amount >= t.amount) {
                            amount -= t.amount;
                            buyHeap.pop();
                        } else if (amount < t.amount) {
                            t.amount -= amount;
                            amount = 0;
                            buyHeap.pop();
                            buyHeap.push({t.price, t.amount, t.orderType});
                            break;
                        }
                    }
                    else if (price > t.price) break;
                }
                if (amount != 0) {
                    sellHeap.push({price, amount, orderType});
                }
            }
        }

        int res = 0;
        while (buyHeap.size()) {
            buyOrders t = buyHeap.top();
            buyHeap.pop();
            res = (res + t.amount) % N;
            // cout << t.price << ", " << t.amount << ", " << t.orderType << endl;
        }

        while (sellHeap.size()) {
            sellOrders t = sellHeap.top(); 
            sellHeap.pop();
            res = (res + t.amount) % N;
            // cout << t.price << ", " << t.amount << ", " << t.orderType << endl;
        }

        return res;
    }
};