当前位置:网站首页>Leetcode T1165: 日志分析
Leetcode T1165: 日志分析
2022-07-07 02:24:00 【范谦之】
日志分析
题目描述
M M M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作:第一类操作为集装箱入库操作,以及该次入库的集装箱重量;第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出,即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。
出于分析目的,分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时,每遇到一次查询操作,都要报告出当前仓库中最大集装箱的重量。
输入格式
包含 N + 1 N+1 N+1 行:
第一行为 1 1 1 个正整数 N N N,对应于日志内所含操作的总数。
接下来的$N $行,分别属于以下三种格式之一:
格式 1 1 1: 0 X 0 X 0X //一次集装箱入库操作,正整数 X X X表示该次入库的集装箱的重量
格式 2 2 2: 1 1 1 //一次集装箱出库操作,(就当时而言)最后入库的集装箱出库
格式 3 3 3: 2 2 2 //一次查询操作,要求分析程序输出当前仓库内最大集装箱的重量
当仓库为空时你应该忽略出库操作,当仓库为空查询时你应该输出 0 0 0。
输出格式
输出行数等于日志中查询操作的次数。每行为一个正整数,表示查询结果。
样例 #1
样例输入 #1
13
0 1
0 2
2
0 4
0 2
2
1
2
1
1
2
1
2
样例输出 #1
2
4
4
1
0
提示
对于 20 % 20\% 20%的数据,有 N ≤ 10 N≤10 N≤10;
对于 40 % 40\% 40%的数据,有 N ≤ 1000 N≤1000 N≤1000;
对于 100 % 100\% 100%的数据,有 N ≤ 200000 , X ≤ 1 0 8 N≤200000,X≤10^8 N≤200000,X≤108。
思路
此题在于维护一个栈a[],实现它的 进栈、出栈、查询操作,以满足题目的要求。该栈需满足 a[i] 为栈底到 i 个元素中最大的。
- 入栈:当入栈一个元素 x,t++,a[t] = max(a[t-1], x)
- 出栈:t–
- 查询:输出a[t]
上述栈可以满足题目要求的关键在于:如果进入的一个元素 x 并不是当前栈内最大的(假设最大的为mx),即之前进入的元素有比它大的,那么我们不关心x的值到底是多少,因为直到它被出栈,也不会被访问,因为访问数会输出mx。如下图:
并且,栈底元素为0,满足题目要求:当仓库为空时输出0.
代码
#include<iostream>
#include<cmath>
using namespace std;
int a[200001], t = 0, y, n, ord;
int main() {
a[0] = 0;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> ord;
if(ord == 0) {
cin >> y;
t+=1;
a[t] = max(a[t-1], y);
}
else if(ord == 1) {
if(t > 0) t-=1;
}
else cout << a[t] << endl;
}
return 0;
}
边栏推荐
- ICML 2022 | 探索语言模型的最佳架构和训练方法
- JVM in-depth
- Calculation model FPS
- Leite smart home longhaiqi: from professional dimming to full house intelligence, 20 years of focus on professional achievements
- 请问如何查一篇外文文献的DOI号?
- uniapp开发小程序如何使用微信云托管或云函数进行云开发
- 一条慢SQL拖死整个系统
- 如何解决数据库插入数据显示SQLSTATE[HY000]: General error: 1364 Field ‘xxxxx‘ doesn‘t have a default value错误
- Developers don't miss it! Oar hacker marathon phase III chain oar track registration opens
- Shared memory for interprocess communication
猜你喜欢
偏执的非合格公司
PostgreSQL database timescaledb function time_ bucket_ Gapfill() error resolution and license replacement
Prompt for channel security on the super-v / device defender side when installing vmmare
ETCD数据库源码分析——从raftNode的start函数说起
A program lets you understand what static inner classes, local inner classes, and anonymous inner classes are
Ant manor safety helmet 7.8 ant manor answer
使用TCP/IP四层模型进行网络传输的基本流程
JWT certification
力扣62 不同路径(从矩阵左上到右下的所有路径数量) (动态规划)
请问如何查一篇外文文献的DOI号?
随机推荐
Stack and queue-p79-10 [2014 unified examination real question]
Matlab / envi principal component analysis implementation and result analysis
网络基础 —— 报头、封装和解包
MySQL(十)
Go straight to the 2022ecdc fluorite cloud Developer Conference: work with thousands of industries to accelerate intelligent upgrading
How can I check the DOI number of a foreign document?
BindingException 异常(报错)处理
【从零开始】win10系统部署Yolov5详细过程(CPU,无GPU)
常用函数detect_image/predict
如何解决数据库插入数据显示SQLSTATE[HY000]: General error: 1364 Field ‘xxxxx‘ doesn‘t have a default value错误
Knight defeats demon king (Backpack & DP)
一段程序让你明白什么静态内部类,局部内部类,匿名内部类
c语言(结构体)定义一个User结构体,含以下字段:
A program lets you understand what static inner classes, local inner classes, and anonymous inner classes are
博士申请 | 上海交通大学自然科学研究院洪亮教授招收深度学习方向博士生
Install mongodb database
Several key steps of software testing, you need to know
Unable to debug screen program with serial port
C面试24. (指针)定义一个含有20个元素的double型数组a
Force deduction 62 different paths (the number of all paths from the upper left to the lower right of the matrix) (dynamic planning)