当前位置: 首页 > news >正文

Leetcode.1801 积压订单中的订单总数

题目链接

Leetcode.1801 积压订单中的订单总数 Rating : 1711

题目描述

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

示例 1:

在这里插入图片描述

输入:orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
输出:6
解释:输入订单后会发生下述情况:
提交 5 笔采购订单,价格为 10 。没有销售订单,所以这 5 笔订单添加到积压订单中。
提交 2 笔销售订单,价格为 15 。没有采购订单的价格大于或等于 15 ,所以这 2 笔订单添加到积压订单中。
提交 1 笔销售订单,价格为 25 。没有采购订单的价格大于或等于 25 ,所以这 1 笔订单添加到积压订单中。
提交 4 笔采购订单,价格为 30 。前 2 笔采购订单与价格最低(价格为 15)的 2 笔销售订单匹配,从积压订单中删除这 2 笔销售订单。第 3 笔采购订单与价格最低的 1 笔销售订单匹配,销售订单价格为 25 ,从积压订单中删除这 1
笔销售订单。积压订单中不存在更多销售订单,所以第 4 笔采购订单需要添加到积压订单中。 最终,积压订单中有 5 笔价格为 10
的采购订单,和 1 笔价格为 30 的采购订单。所以积压订单中的订单总数为 6 。

示例 2:

在这里插入图片描述

输入:orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
输出:999999984
解释:输入订单后会发生下述情况:
提交 109 笔销售订单,价格为 7 。没有采购订单,所以这 109 笔订单添加到积压订单中。
提交 3 笔采购订单,价格为 15 。这些采购订单与价格最低(价格为 7 )的 3 笔销售订单匹配,从积压订单中删除这 3 笔销售订单。
提交 999999995 笔采购订单,价格为 5 。销售订单的最低价为 7 ,所以这 999999995 笔订单添加到积压订单中。
提交 1 笔销售订单,价格为 5 。这笔销售订单与价格最高(价格为 5 )的 1 笔采购订单匹配,从积压订单中删除这 1 笔采购订单。 最终,积压订单中有 (1000000000-3) 笔价格为 7 的销售订单,和 (999999995-1) 笔价格为 5
的采购订单。所以积压订单中的订单总数为 1999999991 ,等于 999999984 % (10^9 + 7) 。

提示:

  • 1<=orders.length<=1051 <= orders.length <= 10^51<=orders.length<=105
  • orders[i].length==3orders[i].length == 3orders[i].length==3
  • 1<=pricei,amounti<=1091 <= pricei, amounti <= 10^91<=pricei,amounti<=109
  • orderTypei01

分析:

我们用两个 来模拟这个过程。堆里面存的是 (price,amount)这样的二元组。

对于 buy订单,用一个 大顶堆 来存储,因为每次要选择最大的 buy订单。

对于 sell订单,用一个 小顶堆 来存储,因为每次要选择最小的 sell订单。

直接模拟这个过程即可。

时间复杂度:O(nlogn)O(nlogn)O(nlogn)

代码:

const int MOD = 1e9+7;
using PII = pair<int,int>;
class Solution {
public:int getNumberOfBacklogOrders(vector<vector<int>>& orders) {priority_queue<PII,vector<PII>,greater<PII>> sell;priority_queue<PII> buy;for(auto o:orders){int price = o[0] , amount = o[1] , type = o[2];//buyif(type == 0){while(!sell.empty() && sell.top().first <= price){if(amount == 0) break;auto [p,cnt] = sell.top();sell.pop();if(cnt <= amount) amount -= cnt;else{cnt -= amount;amount = 0;sell.push({p,cnt});}}if(amount > 0) buy.push({price,amount}); }//sellelse{while(!buy.empty() && buy.top().first >= price){if(amount == 0) break;auto [p,cnt] = buy.top();buy.pop();if(cnt <= amount) amount -= cnt;else{cnt -= amount;amount = 0;buy.push({p,cnt});}}if(amount > 0) sell.push({price,amount});}}int ans = 0;while(!sell.empty()){auto[_,cnt] = sell.top();ans = (ans + cnt) % MOD;sell.pop();}while(!buy.empty()){auto[_,cnt] = buy.top();ans = (ans + cnt) % MOD;buy.pop();} return ans;       }
};

相关文章:

Leetcode.1801 积压订单中的订单总数

题目链接 Leetcode.1801 积压订单中的订单总数 Rating &#xff1a; 1711 题目描述 给你一个二维整数数组 orders&#xff0c;其中每个 orders[i] [pricei, amounti, orderTypei]表示有 amounti笔类型为 orderTypei、价格为 pricei的订单。 订单类型 orderTypei 可以分为两种…...

红帽Linux技术-cp命令

cp是一个复制文件或者目录的命令&#xff0c;其作用是将一个或多个文件或目录从源位置复制到目标位置。 格式&#xff1a;cp [选项] 源文件或目录 目标文件或目录 常用选项&#xff1a; -r&#xff1a;复制目录及其子目录下的所有文件和目录&#xff1b; -p&#xff1a;保留…...

代码随想录算法训练营day41 | 动态规划 01背包问题基础 01背包问题之滚动数组

01背包问题基础 问题描述 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 举个栗子 背包最大重量为4。 物品为&#xff1a; 重量价值…...

MyBatis学习笔记(三) —— MyBatis核心配置文件详解

3、核心配置文件详解 id是唯一标识&#xff0c;不能重复&#xff0c;但是在真正开发过程中&#xff0c;不可能一个项目中同时使用两个环境&#xff0c;肯定会使用其中的某一个&#xff0c;这时候它的default就比较重要了。 default是设置我们当前使用的默认环境的id <?x…...

使用GDAL进行坐标转换

1、地理坐标系与投影坐标系空间参考中主要包含大地水准面、地球椭球体、投影坐标系等几部分内容。地图投影就是把地球表面的任意点&#xff0c;利用一定数学法则&#xff0c;转换到地图平面上的理论和方法&#xff0c;一般有两种坐标系来进行表示&#xff0c;分别是地理坐标系和…...

日常编程中和日期相关的代码和bug

本文主要是Java中和日期时间相隔的几个常用代码函数代码&#xff0c;做了总结&#xff0c;希望在日常编码中&#xff0c;可以帮到大家。 1.计算闰年 记住一个短语&#xff0c;“四年一润&#xff0c;百年不闰&#xff0c;四百再润”&#xff0c;不管换啥语言&#xff0c;相信…...

ATT与Intel汇编语法区别

寄存器、变量&#xff08;常量&#xff09;与立即数 在Intel汇编中&#xff0c;无论是寄存器、变量&#xff08;常量&#xff09;还是立即数&#xff0c;都是直接使用的&#xff0c;例如下列例子中分别加载一个变量&#xff08;常量&#xff09;与立即数到寄存器中&#xff1a…...

Spring Cloud Alibaba全家桶(一)——Spring Cloud Alibaba介绍

前言 本文为 Spring Cloud Alibaba介绍 相关知识&#xff0c;下边将对微服务介绍&#xff08;包括&#xff1a;系统架构演变、微服务架构介绍、常见微服务架构&#xff09;&#xff0c;Spring Cloud Alibaba介绍&#xff08;包括&#xff1a;Spring Cloud Alibaba 的定位、Spri…...

2023年网红营销10大趋势解读:品牌出海必看

前不久influencermarketinghub发布了《2023年影响者营销基准报告》&#xff0c;报告总结了3500多家营销机构、品牌和其他相关专业人士对当前网红营销现状的看法&#xff0c;以及预测了未来网红营销的一个发展趋势。本期Nox聚星就带领大家详细解读关于2023年网红营销的10大趋势。…...

Java学习笔记 --- 正则表达式

一、体验正则表达式 package com.javase.regexp;import java.util.regex.Matcher; import java.util.regex.Pattern;/*** 体验正则表达式&#xff0c;给文本处理带来哪些便利*/ public class Regexp_ {public static void main(String[] args) {//假设&#xff0c;编写了爬虫&…...

【基础算法】字符串哈希

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…...

unity 多个模型或物体无限循环拖拽 类似无限列表循环

using System.Collections; using System.Collections.Generic; using UnityEngine; public class ModelAnimal : MonoBehaviour { //需滑动的物体 public GameObject m_objA; //音乐 public GameObject m_objB; //电话 public GameObject m_objC; //导航 public GameObject m…...

GroupDocs.Merger for Java

GroupDocs.Merger for Java GroupDocs.Merger for Java是一个文档操作API&#xff0c;可帮助您合并、拆分、交换或删除文档页面。API通过启用或禁用密码提供保护&#xff0c;并允许开发人员加入PDF、Microsoft Word、Excel和Powerpoint文档。 支持的文件格式 Microsoft Office格…...

04--WXML

1、什么是WXML什么是Wxml呢&#xff1f;我们首先要介绍一下Html&#xff0c;Html的全称为HyperTextMarkup Language&#xff0c;翻译过来就是超文本标记语言&#xff0c;这种语言目前已经普遍用于前端开发&#xff0c;而wxml正是从html演变而来&#xff0c;它基于微信这个平台&…...

一篇五分生信临床模型预测文章代码复现——FIgure 9.列线图构建,ROC分析,DCA分析 (五)

之前讲过临床模型预测的专栏,但那只是基础版本,下面我们以自噬相关基因为例子,模仿一篇五分文章,将图和代码复现出来,学会本专栏课程,可以具备发一篇五分左右文章的水平: 本专栏目录如下: Figure 1:差异表达基因及预后基因筛选(图片仅供参考) Figure 2. 生存分析,…...

每月一书(202302)《狂飙》

文章目录剧情内容观看收获正菜很硬配菜很足食物还有喻义又到了每月一书的时间&#xff0c;本月没有阅读书籍&#xff0c;不过看了一部叫《狂飙》的电视剧&#xff0c;因为该电视剧热度高&#xff0c;所以我也凑个热闹。下面分享一下我看完后的体会。 剧情内容 这是一部扫黑和…...

wsl2 docker 安装

一. 更换镜像源 备份默认源&#xff1a; cp /etc/apt/sources.list /etc/apt/sourses.list.bak 编辑文件&#xff1a; vim /etc/apt/sources.list 删除原有内容并替换为&#xff1a; # 默认注释了源码镜像以提高 apt update 速度&#xff0c;如有需要可自行取消注释 deb …...

极光笔记 | 埋点体系建设与实施方法论

PART 01 前 言随着网络技术的发展&#xff0c;从粗犷型到精细化运营型&#xff0c;再到现在的数字化运营&#xff0c;数据变得越来越细分和重要&#xff0c;不仅可以进行策略调整&#xff0c;还可以实现自动化的精细化运营。而数据价值的起点就是埋点&#xff0c;只有合理地埋点…...

SpringMVC中的各注解类理解

目录 一、概念 二、springmvc注解详解 &#xff08;一&#xff09;控制层注解 1.Controller 2.RequestMapping 3.ResponseBody &#xff08;二&#xff09;配置类&#xff08;bean类&#xff09;注解 4.configuration 5.Bean 一、概念 在学习springmvc的时候&#x…...

DNF搭建服务器服务端搭建教程

DNF搭建服务器服务端搭建教程 我是艾西&#xff0c;今天给大家分享下怎么样自己搭建一个DNF。 前阵子体验了下其他GM搭建的服&#xff0c;那么对于自己搭建的好处在于出道即巅峰&#xff01; 想要什么武器就是一串代码命令的事情。 下面我跟大家说一下需要准备那些东西&#x…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...