What is monotonic queue

What is a monotonic queue

Monotonic queue refers to the monotonicity of the relationship between the elements in the queue , and , The head and tail of the team can be out of the team , Only the tail of the team can join the team .

The typical problem of monotonic queues is sliding windows , So take sliding window as an example to briefly introduce monotonic queue

Example

Given a size of  n≤1e6  Array of .

There is a size of  kk Sliding window of , It moves from the far left to the far right of the array .

You can only see in the window  k  A digital .

Move 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  by  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 make sure that the sliding window is in each position , Maximum and minimum values in the window .

Input format

The input contains two lines .

The first line contains two integers  n  and  k, Represents the length of the array and the length of the sliding window .

The second line has  n  It's an integer , Represents the specific value of an array .

Separate peer data with spaces .

Output format

The output contains two .

The first line outputs , From left to right , Minimum value in each position slide window .

The second line outputs , From left to right , Maximum value in each position slide window .

sample input ：

8 3
1 3 -1 -3 5 3 6 7

sample output ：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

Ideas

The idea of monotone queue and monotone stack is the same , Let's first think about how to do violence , Then delete the useless ones , We can get monotonicity ,  If there is monotonicity, let's find the extreme value , Then the time complexity of enumeration can be changed into O(1)

The practice of violence is that we use queues to maintain this window , Insert new elements at the end of the team every time , Elements that slide out bounce out of the tail of the team . Each time we find the extreme value, we directly traverse all the elements in the queue , This time complexity is O(k), So our whole time complexity is O(nk), The worst case scenario is O(n²). Then we will consider how to optimize , Similar to monotone stack , Let's consider whether some elements in the queue are useless , Then we delete these useless elements to see if we can get monotonicity .

Take the example , When our queue is 3,-1,-3 when , It can be found that as long as -3 In the queue , that 3,-1 It will not be output as an answer . So we can find , As long as the number at the front of our queue is larger than the number at the back , Then we can judge that the previous number must be useless , As long as we have this reverse order right , We can delete large numbers , Delete all such pairs in reverse order , The whole series will become a strictly monotonous rising series . What we seek is the minimum value in this queue , The minimum value of a strictly monotonically rising queue is our team leader , So every time you find the minimum value, you can directly find the team leader .

There is also the judgment of when the team leader element will leave the team ? For this question ,i Is the right endpoint of enumeration ,k Is the interval length , Note that there are subscripts in the queue , See if the subscript of the team leader is (i-k+1,i) Just within the scope .

So the monotone stack and monotone queue are similar , We all consider using stack and queue violence to solve this problem first , Then consider deleting useless elements to see if there is monotonicity , If the remaining elements are monotonic, we can consider optimization .

We also use arrays to simulate queues , Because it's faster .

Code implementation

#include <iostream>
using namespace std;
const int N=1e6+10;
int a[N],q[N];//a Represents the given array ,q Represents a queue 
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    cin>>a[i];
    int hh=0,tt=-1;// Team head and tail 
    for(int i=0;i<n;i++)
    {
        // If the team leader has slipped out of the window 
        if(hh<=tt&&i-k+1>q[hh]) hh++;
        // For the minimum , Determine whether the number of inserts is smaller than the tail element 
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        // front k The number does not need to be output 
        if(i>=k-1)
        cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    hh=0,tt=-1;
    // The maximum and minimum values are similar 
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-k+1>q[hh]) hh++;
        // For maximum , Judge that the number of inserts is larger than the tail element 
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1)
        cout<<a[q[hh]]<<" ";
    }
}