Leetcode t1165: log analysis

Log analysis

Title Description

$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$ That's ok ：

First act $1$ A positive integer $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$: $0X$ // One container warehousing operation , Positive integer $X$ Indicates the weight of the container in this warehouse

Format $2$: $1$ // One container outbound operation ,（ For the time being ） The last container in the warehouse leaves the warehouse

Format $3$: $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$.

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\%$ The data of , Yes $N\le 10$;

about $40\%$ The data of , Yes $N\le 1000$;

about $100\%$ The data of , Yes $N\le 200000,X\le 10^8$.

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 .

1. Push ： When you stack an element x,t++,a[t] = max(a[t-1], x)
2. Out of the stack ：t–
3. 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;   
}