catalogue
1, Code operation of stack and queue
1. AcWing 828 simulation stack
1, Code operation of stack and queue
1. AcWing 828 simulation stack
Implement a stack. The stack is initially empty and supports four operations:
- push x – insert a number # x to the top of the stack;
- Pop – pop a number from the top of the stack;
- Empty – judge whether the stack is empty;
- Query – query the top element of the stack.
Now we need to perform M # operations on the stack, in which each operation # 3 # and operation # 4 # should output the corresponding results.
Input format
The first line contains the integer M, indicating the number of operations.
Next, there are # M # lines. Each line contains an operation command. The operation command is one of # push x, pop, empty, query #.
Output format
For each "empty" and "query" operation, a query result should be output, and each result occupies one row.
Where, the query result of empty ， operation is ， YES ， or ， NO, and the query result of query ， operation is an integer representing the value of the top element of the stack.
Data range
1≤M≤100000
1≤x≤109
All operations are legal.
Input sample:
10 push 5 query push 6 pop query pop empty push 4 query empty
Output example:
5 5 YES 4 NO
#include<iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;//stk[N] is the array simulation stack, tt is the pointer pointing to the top element of the stack
int main()
{
int m;
cin >> m;
while (m -- )
{
string op;
cin >> op;
//insert
if (op == "push")
{
int x;
cin >> x;
stk[ ++ tt] = x;
}
else if (op == "pop") tt -- ;//eject
else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;//Determine whether the stack is empty
else cout << stk[tt] << endl;//Output stack top element
}
return 0;
}2. AcWing 829 analog queue
Implement a queue. The queue is initially empty and supports four operations:
- push x – insert a number # x to the end of the team;
- Pop – pop a number from the head of the team;
- Empty – judge whether the queue is empty;
- Query – query the queue header element.
Now we need to perform M # operations on the queue, and each of the operations # 3 # and # 4 # should output the corresponding results.
Input format
The first line contains the integer M, indicating the number of operations.
Next, there are # M # lines. Each line contains an operation command. The operation command is one of # push x, pop, empty, query #.
Output format
For each "empty" and "query" operation, a query result should be output, and each result occupies one row.
Where, the query result of empty operation is YES or NO, and the query result of query operation is an integer representing the value of the queue head element.
Data range
1≤M≤100000
1≤x≤109
All operations shall be legal.
Input sample:
10 push 6 empty query pop empty push 3 push 4 pop query push 6
Output example:
NO 6 YES 4
#include<iostream>
using namespace std;
const int N = 100010;
int q[N], hh, tt = -1;//hh points to the team head element and tt points to the team tail element
int main()
{
int m;
cin >> m;
while (m -- )
{
string op;
cin >> op;
//Insert element at end of queue
if (op == "push")
{
int x;
cin >> x;
q[ ++ tt] = x;
}
else if (op == "pop") hh ++ ;//Pop up the queue header element. Note that this is + + instead of--
else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;//Judge whether the queue is empty
else cout << q[hh] <<endl;//Output header element
}
return 0;
}2, Monotone stack
Monotone stack is more abstract, but there are not many question types that will be investigated. Almost only the question types such as AcWing 830 are investigated, so I only train for the question.
1. AcWing 830 monotone stack
Given a sequence of integers with a length of − N ， output the first number smaller than it on the left of each number. If it does not exist, output − 1.
Input format
The first row contains the integer N, which represents the length of the sequence.
The second row contains N # integers, representing the integer sequence.
Output format
A total of one line, including − N integers, where the − i − number represents the first number smaller than it on the left of the − i − number. If it does not exist, it outputs − 1.
Data range
1≤N≤105
1 ≤ element in sequence ≤ 109
Input sample:
5 3 4 2 7 5
Output example:
-1 3 -1 2 2
#include<iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
int m;
cin >> m;
while (m -- )
{
int x;
cin >> x;
while (tt && stk[tt] >= x) tt -- ;
if (!tt) cout << "-1 ";
else cout << stk[tt] << " ";
stk[ ++ tt] = x;
}
return 0;
}The so-called monotone stack is actually a tool used to output the nearest number to the left of each number that is smaller than it. For each number in the sequence, we first make a judgment before entering the stack: if the stack is empty, there is no number on the left, let alone find a number smaller than x; If the stack is not empty and the top element is greater than or equal to x, the top element will pop up (because the top element will never be output due to the existence of X, leaving it in the stack will hinder). By constantly popping up stack top elements larger than x, the stack top elements must be smaller than X after the while loop ends. The stack obtained by this operation can keep the elements monotonically increasing all the time, so it is called monotonic stack.
3, Monotone queue
1. AcWing 154 sliding window
Give an array with a size of n ≤ 106.
There is a sliding window with the size of ， k ， which moves from the leftmost to the rightmost of the array.
You can only see k# numbers in the window.
Slide the window one position to the right at a time.
Here is an example:
The array is [1 3 - 1 - 3 5 3 6 7], and k is 3.
| window position | minimum value | Maximum |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
Your task is to determine the maximum and minimum values in the window when the sliding window is in each position.
Input format
The input contains two lines.
The first line contains two integers n and k, representing the length of the array and the length of the sliding window, respectively.
The second line has n # integers representing the specific values of the array.
Peer data is separated by spaces.
Output format
The output contains two.
The first line outputs the minimum value in the sliding window from left to right in each position.
The second line outputs the maximum value in the sliding window from left to right in each position.
Input sample:
8 3 1 3 -1 -3 5 3 6 7
Output example:
-1 -3 -3 -3 3 3 3 3 5 5 6 7
Before using monotone queue optimization, the time complexity of violent practice is O(nk).
#include<iostream>
using namespace std;
const int N = 1000010;
int n;
int a[N], q[N];
int main()
{
int k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
//This ensures that the elements in the queue are always a subset of the elements in the window
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
//Ensure that the queue increases monotonically, that is, the queue head element is the minimum value of the element in the window
q[ ++ tt] = i;
//q[N] the array stores the subscripts of the elements of the sequence
if (i >= k - 1) printf("%d ", a[q[hh]]);
//When I > = k-1 (the starting position where the window is filled with elements), the queue head element is output
//a[q[hh]] represents the smallest number of window elements
}
puts("");//enter
hh = 0, tt = -1;//initialization
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
//Ensure that the queue decreases monotonically, that is, the queue head element is the maximum value of the element in the window
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
//When I > = k-1 (the starting position where the window is filled with elements), the queue head element is output
//a[q[hh]] indicates the maximum number of values in the window element
}
puts("");//enter
return 0;
}HH < = TT can ensure that the statement is not executed when the queue is empty, and the elements are added into the queue first.