本文共 3918 字，大约阅读时间需要 13 分钟。

原题指路

题目描述

给你一个二维整数数组 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 将会添加到积压订单中。
  输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对 1e9 + 7 取余的结果。

解题思路

代码

struct order//先定义一个order结构体，指定两类订单不同的排序顺序{       int price, amount, type;    friend bool operator< (order n1, order n2)    {           if(n1.type == 0)            return n1.price < n2.price;        else            return n1.price > n2.price;    }};class Solution {       public:        priority_queue
   
     buy;        priority_queue
    
      sell;        int getNumberOfBacklogOrders(vector
     
      
       >& orders)         {               int mod = 1e9 +7;            for(int i = 0; i < orders.size(); i++)//主要过程就是在插入同时不断去维护这两个优先队列                if(orders[i][2] == 0)                {                       while(!sell.empty() && sell.top().price <= orders[i][0])                    {                           if(sell.top().amount < orders[i][1])                        {                               orders[i][1] -= sell.top().amount;                            sell.pop();                        }                        else if(sell.top().amount == orders[i][1])                        {                               sell.pop();                            orders[i][1] = 0;                            break;                        }                        else if(sell.top().amount > orders[i][1])                        {                               order temp = sell.top();                            sell.pop();                            temp.amount -= orders[i][1];                            sell.push(temp);                            orders[i][1] = 0;                            break;                        }                    }                    if(orders[i][1])                        buy.push({   orders[i][0], orders[i][1], orders[i][2]});                }                else                {                       while(!buy.empty() && buy.top().price >= orders[i][0])                    {                           if(buy.top().amount < orders[i][1])                        {                               orders[i][1] -= buy.top().amount;                            buy.pop();                        }                        else if(buy.top().amount == orders[i][1])                        {                               buy.pop();                            orders[i][1] = 0;                            break;                        }                        else if(buy.top().amount > orders[i][1])                        {                               order temp = buy.top();                            buy.pop();                            temp.amount -= orders[i][1];                            buy.push(temp);                            orders[i][1] = 0;                            break;                        }                    }                    if(orders[i][1])                        sell.push({   orders[i][0], orders[i][1], orders[i][2]});                }            int sum = 0;            while(!sell.empty())            {                   sum = (sum + sell.top().amount % mod) % mod;                sell.pop();            }            while(!buy.empty())            {                   sum = (sum + buy.top().amount % mod) % mod;                buy.pop();            }            return sum;        }};