Stack and Queue
1. Differences
2. Definition of stack
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; int stk[N],tt; //insert stk[++tt]=x; //Eject tt--; //Determine if stack is empty if(tt>0) not empty else empty //Top of Stack stk[tt];
3. Queue Definition
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; //Insert element at end of queue, eject element at head int q[N],hh,tt = -1;//hh for the head and tt for the tail //insert q[++tt]=x; //Eject hh++; //Determine whether it is empty if(hh<=tt) not empty else empty //Remove the queue head element q[hh] //Remove the tail element q[tt]
Picture in the form of Queue Popup_
4. Monotonic Stack
Given an integer column of length N, output the first number to the left of each number smaller than it, or output 1 if it does not exist.
Input Format
The first row contains the integer N, which represents the length of the column.
The second row contains N integers, representing an integer column.
Output Format
A row containing N integers, where the number i represents the first number to the left of the number i that is smaller than it and outputs 1 if it does not exist.
Data Range
1 ≤ N ≤ 105
Elements in columns 1 or less < 109
Input sample:
5 3 4 2 7 5
Output sample:
-1 3 -1 2 2
thinking
-
Violent practices
-
Monotonic stack practices_
AC Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int stk[N],tt;
int main()
{
cin>>n;
//Delete all points in reverse order, and the remaining points must monotonically increase
for(int i=0;i<n;i++)
{
int x;
cin>>x;
while(tt && stk[tt]>=x)
{
tt--;
}
if(tt)
{
cout<<stk[tt]<<' ';
}
else
{
cout<<-1<<" ";
}
stk[++tt] = x;
}
}
5. Monotonic Queue (Sliding Window)
Given an array of size n < 106.
There is a sliding window of size k that moves from the leftmost to the rightmost side of the array.
You can only see k numbers in the window.
Slide the window one position to the right each time.
Here is an example:
The array is [1 3-1-3 5 3 6 7], 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 sliding window at each location.
Input Format
The input contains two lines.
The first row contains two integers, n and k, representing the length of the array and the length of the sliding window, respectively.
The second row 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 of output, from left to right, slides the minimum value in the window at each location.
The second line of output, from left to right, slides the maximum value in the window at each location.
Input sample:
8 3 1 3 -1 -3 5 3 6 7
Output sample:
-1 -3 -3 -3 3 3 3 3 5 5 6 7
thinking
Two steps for each move:
- Insert new elements at the end of the queue
- Elements that slip out pop up from the end of the queue
Violent practices: iterate directly through all elements of the queue
Practices for monotonic stacks and queues:
They use violence to simulate the problem first, then find out which elements in the stack and queue are not useful in the simple algorithm, delete all the useful elements, and then see if they are monotonic. If the remaining elements are monotonic, they can be optimized. If you take the extreme value, it becomes two endpoints. If you find a value, you can use two points...
AC Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
int a[N],q[N];
int main()
{
int n,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++)
{
//Determine if the team leader has slid out of the window
if(hh <= tt && i - k + 1 > q[hh])//The window will only go one bit to the right, so only one last number is not in the window at a time
{
hh ++;
}
while(hh <= tt && a[q[tt]] >= a[i])
{
tt --;
}
q[ ++ tt] = i;
if(i >= k-1)
{
printf("%d ",a[q[hh]]);
}
}
puts("");
hh = 0, tt = -1;
for(int i=0;i<n;i++)
{
//Determine if the team leader has slid out of the window
if(hh <= tt && i - k + 1 > q[hh])//The window will only go one bit to the right, so only one last number is not in the window at a time
{
hh ++;
}
while(hh <= tt && a[q[tt]] <= a[i])
{
tt --;
}
q[ ++ tt] = i;
if(i >= k-1)
{
printf("%d ",a[q[hh]]);
}
}
puts("");
return 0;
}