当前位置: 首页 > 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…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...