1801. Number of Orders in the Backlog

周賽複盤

說真的每次看到類似的題目我覺得就是來拖台錢的

我們用兩個priority_queue, 分別是max heap, 跟min heap

我們要買時, 如果賣價太高, 我們就掛買, 但如果賣價小於等於買價, 就可以直接削掉賣價單

我們要賣時, 如果買價太低, 我們就掛賣, 如果買價大於等於賣價, 就可以直接消去買價單

相信有玩股票的朋友應該都很了解XD

由於直接一張一張看太慢, 所以我們就用{價格, 單數來看}

這題思想還蠻簡單的, 但就是寫起來複雜也容易錯

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        priority_queue<pair<int, long>> buyer;
        priority_queue<pair<int, long>, vector<pair<int, long>>, greater<pair<int, long>>> seller;
        for(auto &o: orders){
            // pricei, amounti, orderTypei
            int p = o[0];
            long amount = o[1];
            int orderT = o[2];
            // buy
            if(orderT == 0){
                while(!seller.empty() && amount > 0){
                    auto s = seller.top();
                    if(s.first <= p){
                        if(s.second >= amount){
                            s.second -= amount;
                            seller.pop();
                            amount = 0;
                            if(s.second != 0) seller.push({s.first, s.second});
                            break;
                        }else{
                            amount -= s.second;
                            seller.pop();
                        }
                    } else{
                      break;
                    }
                }
                if(amount > 0){
                    buyer.push({p, amount});
                }
                
            } else {
                //sell
                while(!buyer.empty() && amount > 0){
                    auto s = buyer.top();
                    if(s.first >= p){
                        if(s.second >= amount){
                            s.second -= amount;
                            buyer.pop();
                            amount = 0;
                            if(s.second != 0)  buyer.push({s.first, s.second});
                            break;
                        }else{
                            amount -= s.second;
                            buyer.pop();
                        }
                    }else{
                      break;
                    }
                }
                if(amount > 0){
                    seller.push({p, amount});
                }
               
            }
        }
        long res = 0;
        while(!buyer.empty()){
            auto t = buyer.top();
            buyer.pop();
            res += t.second;
        }
        while(!seller.empty()){
            auto t = seller.top();
            seller.pop();
            res += t.second;
        }
        long m = (1e9 + 7);
        return res % m;
    }
};