Sliding window + monotone queue concept and example (p1886 Logu)

（ Guangdong University of Technology ACM Project Study 1 ）

The sliding window

Sliding window algorithm （ Also called ruler ） The concept of is actually very simple , In many cases, it is necessary to combine more knowledge to solve problems , For example, monotonic queues .
What is a sliding window ： In a computer network , Sliding window algorithm is a technique used to improve throughput . In the algorithm, it is to maintain a window composed of left and right pointers in strings or arrays （ Variable or fixed window size ）, Operations in the window .

A monotonous queue

Also called double ended queue , Simply put, it means joining and leaving the team from time to time , Ensure that the queue elements are monotonic .

Project Study 1 The sliding window
Let's focus on how to maintain a monotonic queue .
There's a long one for n Sequence a, And a size of k The window of . Now this one slides from the left to the right , Slide one unit at a time , Find the maximum and minimum values in the window after each slide .

Input format
There are two lines of input , The first line has two positive integers n,k. The second line n It's an integer , Represents a sequence a.
Output format
The output consists of two lines , The first line is the minimum value of each window slide
The second line is the maximum value of each window sliding
Input ：

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

Output ：

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

analysis ：
The question is The sliding window + A monotonous queue The template question of .

We know that as long as every window is moved , Output the maximum value ; So how do we find the best value for each window ？ If violence Words , We can move the window every time Traverse The whole window looks for the best value , But every time you move, you traverse , It is equivalent to traversing the window position and the elements in the window , You can imagine the complexity .

So we only know The sliding window It's not enough , Here we still need to learn A monotonous queue To solve .

( Let's first look for the minimum )
Maintain a A monotonous queue , In this queue nature From the head of the queue to the tail of the queue, the elements must be incremented while traversing the array , The subscript of the element in the queue in the array must be Monotone increasing Of （ Because every time I go in from the end of the team ）, and Team head Is the smallest element .
Each time we traverse an element, let him and the tail of the team judge ; If this element is larger than the tail element , It shows that if the elements are queued, they can still remain monotonous ; If this element is smaller than the tail , That is, if this element is in the team , The queue is not monotonous , Here we are going to kick out the tail element （ Another way ： Follow the thinking of finding the best value , If the tail element is larger than the added element , Then the tail element has no potential to become the minimum ）, meanwhile , Don't forget that the window size is limited , If the difference between the subscript of the header element and the subscript of the footer element is greater than the window size , You have to kick out the team leader element .
Next, let's simulate the example .（ Queue takes array elements as elements , It can also be subscripted as an element , Not here. ）

Be careful ： Red in the picture X Is the element kicked out .
Be careful ： We have to wait until i Traversing k（ That's the window size ）, It's just beginning to output .
Pictured ：
① Traversing elements 1,1 The team , No element is out of the team .
② Traversing elements 3,3 Larger than the tail of the team 1,3 The team , No element is out of the team .
③ Traversing elements -1,-1 Less than the tail of the team 3,3 Out of the team , Judge again ,-1 Less than the new team tail 1,1 Out of the team ,-1 The team .
④ Traversing elements -3,-3 Less than the tail of the team -1,-1 Out of the team ,-3 The team .
⑤ Traversing elements 5,5 Greater than -3,5 The team , No element is out of the team .
And so on , Traversing 3 when ,3 Less than 5,5 Out of the team , Judge again ,3 Greater than -3,3 The team .
This process maintains a monotonous queue , But not enough .

Let's look at the last line , If according to the above judgment ,6 You can join the team , But take a closer look at the sample , The window size is 3,-3 To 6 Overflow window closed , So every time we judge, we need to add a window length maintenance .
Create a new queue , Every time the element enters the team , The subscript is also in the team .
Add an operation at this time
① Traversing elements 1,1 The team ,( The difference between the leading and trailing subscripts is less than 3) No element is out of the team .
② Traversing elements 3,3 Larger than the tail of the team 1,3 The team ,（ The difference between the leading and trailing subscripts is less than 3） No element is out of the team .
③ Traversing elements -1,-1 Less than the tail of the team 3,3 Out of the team , Judge again ,-1 Less than the new team tail 1,1 Out of the team ,（ The difference between the leading and trailing subscripts is less than 3）-1 The team .
④ Traversing elements -3,-3 Less than the tail of the team -1,-1 Out of the team ,-3 The team （ The difference between the leading and trailing subscripts is less than 3）.
⑤ Traversing elements 5,5 Greater than -3,5 The team ,（ The difference between the leading and trailing subscripts is less than 3） No element is out of the team .
And so on , Traversing 3 when ,3 Less than 5,5 Out of the team , Judge again ,3 Greater than -3,3 The team .
Traversing 6,6 The team ,（ The difference between the leading and trailing subscripts is equal to 3） Kick out the team leader element -3.
As long as the queue header is output for each iteration, the sequence can be obtained , The maximum value only needs to change a symbol when judging .
Reference code ：

#include <iostream>// Use arrays to simulate queues 
using namespace std;
int a[1000002];
int q[1000002];
int x[1000002];
int q1[1000002];
int x1[1000002];
int head=1,tail=0;
int main()
{
    
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
    // Minimum 
        while(head<=tail && x[head]+k<=i)head++;//head Moving right means kicking out of the team 
        while(head<=tail && q[tail]>a[i])tail--;//tail Moving left means kicking out the tail of the team 
        q[++tail]=a[i];// The tail of the team moves to the right and the elements join the team 
        x[tail]=i;
        if(i>=k)printf("%d ",q[head]);
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
    // Maximum 
        while(head<=tail && x1[head]+k<=i)head++;
        while(head<=tail && q1[tail]<a[i])tail--;
        q1[++tail]=a[i];
        x1[tail]=i;
        if(i>=k)printf("%d ",q1[head]);
    }
}