当前位置:网站首页>Leetcode t1165: log analysis
Leetcode t1165: log analysis
2022-07-07 07:00:00 【Fan Qianzhi】
Log analysis
Title Description
M M M The shipping company recently needs to make statistics on the import and export of goods in its warehouses . At present, the only record they have is a log recording the entry and exit of containers . The log records two types of operations : The first type of operation is container warehousing , And the weight of the container in the warehouse ; The second type of operation is the outbound operation of containers . These records are in strict chronological order . The rules of container warehousing and outbound are first in and last out , That is, the containers to be delivered in each delivery operation are the latest containers to be delivered in the warehouse .
For analytical purposes , The analyst randomly inserts several third types of operations into the log ―― Query operation . When analyzing logs , Every query operation encountered , Report the weight of the largest container in the current warehouse .
Input format
contain N + 1 N+1 N+1 That's ok :
First act 1 1 1 A positive integer N N N, Corresponds to the total number of operations contained in the log .
Next $N $ That's ok , They belong to one of the following three formats :
Format 1 1 1: 0 X 0 X 0X // One container warehousing operation , Positive integer X X X Indicates the weight of the container in this warehouse
Format 2 2 2: 1 1 1 // One container outbound operation ,( For the time being ) The last container in the warehouse leaves the warehouse
Format 3 3 3: 2 2 2 // One query operation , The analyzer is required to output the weight of the largest container in the current warehouse
When the warehouse is empty, you should ignore the issue operation , When the warehouse is empty, you should output 0 0 0.
Output format
The number of output rows is equal to the number of query operations in the log . Each line is a positive integer , Represents the query result .
Examples #1
The sample input #1
13
0 1
0 2
2
0 4
0 2
2
1
2
1
1
2
1
2
Sample output #1
2
4
4
1
0
Tips
about 20 % 20\% 20% The data of , Yes N ≤ 10 N≤10 N≤10;
about 40 % 40\% 40% The data of , Yes N ≤ 1000 N≤1000 N≤1000;
about 100 % 100\% 100% The data of , Yes N ≤ 200000 , X ≤ 1 0 8 N≤200000,X≤10^8 N≤200000,X≤108.
Ideas
This problem is to maintain a stack a[], To achieve it Into the stack 、 Out of the stack 、 Query operation , To meet the requirements of the topic . This stack needs to meet a[i] From the bottom of the stack to i The largest of the elements .
- Push : When you stack an element x,t++,a[t] = max(a[t-1], x)
- Out of the stack :t–
- Inquire about : Output a[t]
The key that the above stack can meet the requirements of the topic is : If you enter an element x Not the largest in the current stack ( Suppose the biggest one is mx), That is, the element that entered before is larger , Then we don't care x What is the value of , Because until it is out of the stack , Will not be visited , Because the number of accesses will be output mx. Here's the picture :
also , The elements at the bottom of the stack are 0, Meet the requirements of the topic : Output when the warehouse is empty 0.
Code
#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;
}
边栏推荐
猜你喜欢
从零到一,教你搭建「CLIP 以文搜图」搜索服务(二):5 分钟实现原型
Big coffee gathering | nextarch foundation cloud development meetup is coming
How can gyms improve their competitiveness?
JESD204B时钟网络
健身房如何提高竞争力?
SVN version management in use replacement release and connection reset
Stack and queue-p78-8 [2011 unified examination true question]
MOS tube parameters μ A method of Cox
Please answer the questions about database data transfer
Redhat5 installing vmware tools under virtual machine
随机推荐
基于JS的迷宫小游戏
oracle如何备份索引
Please ask a question, flick Oracle CDC, read a table without update operation, and repeatedly read the full amount of data every ten seconds
How to share the same storage among multiple kubernetes clusters
品牌·咨询标准化
What books can greatly improve programming ideas and abilities?
学术报告系列(六) - Autonomous Driving on the journey to full autonomy
Sqlserver multithreaded query problem
华为机试题素数伴侣
ip地址那点事
Learning notes | data Xiaobai uses dataease to make a large data screen
Abnova循环肿瘤DNA丨全血分离,基因组DNA萃取分析
Postgresql源码(60)事务系统总结
2022/07/04学习记录
常用函数detect_image/predict
请教一个问题,flink oracle cdc,读取一个没有更新操作的表,隔十几秒就重复读取全量数据
Tool class: object to map hump to underline underline hump
使用net core优势/为什么使用
How can clothing stores make profits?
from . onnxruntime_ pybind11_ State Import * noqa ddddocr operation error