堆&&优先队列&&TreeMap
2024-09-08 00:39:58
题目描述
题解
题目不难，主要是要读懂题意，一步步模拟，代码较长，需要细心检查。
坑较多，比如我犯了很多傻逼问题：想都不想就拿1<<9+7当作1000000007,更傻逼的是,<<的优先级低于+号,<<都没用对。
实时取最大和最小，可以用堆或者优先队列实现。这里我使用了Java的TreeMap。
class Solution {
public static int getNumberOfBacklogOrders(int[][] orders) {
TreeMap<Integer,Long> sells = new TreeMap<>();//价格：数量
TreeMap<Integer,Long> buys = new TreeMap<>();//价格：数量
for(int i=0;i<orders.length;i++){
if(orders[i][2]==0){//buy
long curBuyAmount = orders[i][1];
int buyPrice = orders[i][0];
while (curBuyAmount>0){
if(sells.isEmpty()){
buys.put(buyPrice,buys.getOrDefault(buyPrice,0l)+curBuyAmount);//添加剩余的订单到积压订单
break;
}
if(sells.firstKey()<=buyPrice){
if(curBuyAmount<sells.get(sells.firstKey())){
sells.put(sells.firstKey(),sells.get(sells.firstKey())-curBuyAmount);
curBuyAmount = 0;
}else{
curBuyAmount -= sells.get(sells.firstKey());
sells.remove(sells.firstKey());
}
}else{
buys.put(buyPrice,buys.getOrDefault(buyPrice,0l)+curBuyAmount);//添加剩余的订单到积压订单
break;
}
}
}else{//sell
long curSellAmount = orders[i][1];
int sellPrice = orders[i][0];
while (curSellAmount>0){
if(buys.isEmpty()){
sells.put(sellPrice,sells.getOrDefault(sellPrice,0l)+curSellAmount);
break;
}
if(buys.lastKey()>=sellPrice){
if(curSellAmount<buys.get(buys.lastKey())){
buys.put(buys.lastKey(),buys.get(buys.lastKey())-curSellAmount);
curSellAmount = 0;
}else{
curSellAmount -= buys.get(buys.lastKey());
buys.remove(buys.lastKey());
}
}else{
sells.put(sellPrice,sells.getOrDefault(sellPrice,0l)+curSellAmount);//添加剩余的订单到积压订单
break;
}
}
}
}
long mod = 1000000007;
long overStockNum = 0;
for(Long i:buys.values()){
overStockNum = (overStockNum + i)%mod;//实时取模
}
for(Long i:sells.values()){
overStockNum = (overStockNum + i)%mod;
}
return (int)(overStockNum%mod);
}
}
最新文章
- Flex 布局教程：语法篇[转]
- 布局两列div等高方法
- zoj 3329 One Person Game 概率DP
- Jsp页面里引入一个javascript文件，在jsp的onclick里怎么添加脚本文件里的方法
- R学习笔记
- iOS开发-大文件下载与断点下载思路
- 团队作业8——第二次项目冲刺（Beta阶段）Day1--5.18
- JavaEE学习路线
- VS2012编译log4cpp1.1.1版本
- pyspider安装提示：got an unexpected keyword argument 'io_loop'的解决办法
- centos 6.5环境下分布式文件系统MogileFS工作原理及分布式部署实现过程
- Java 使用命令对堆线程分析
- tesseract-ocr识别中文扫描图片实例讲解
- SEO笔记：Anatomy of a URL
- C++中的STL中map用法详解(转)
- phpredis 中文手册和redis 教程
- cookies分类
- 【BZOJ】1218: [HNOI2003]激光炸弹（前缀和）
- linux grep日志查询
- jquery colsest的用法