Sliding window maximum value problem

Basic ideas

When calculating the maximum value of the array window , You need to maintain a two-way queue ; For the maximum value problem, it is necessary to ensure the absolute decrease of the queue in the maintenance process ;

• step ： Two The pointer L and R;
  1） The pointer R When you move right , Add the passed index to the queue , And determine the operation according to the existing index in the queue , When adding elements to the end of the queue , Make sure that the element corresponding to the index value to be added is absolutely smaller than the element corresponding to the index value at the end of the queue ; If you don't do that , So take the end of the queue Index value popup for , Add... Until the conditions are met ;
  2） The pointer L When you move right ,L The index value corresponding to the element passed by the pointer has expired in the queue , Judge whether the invalid element is the first element of the current queue , If so , Just pop up from the head of the team ;

Call ： Maintain the index corresponding to the largest element of the current window ;

Example

#include<iostream>
#include<deque>
#include<vector>
using namespace std;

int main()
{
    
	vector<int> res;
	deque<int> que_idx;
	int S = 3;// Window size 
	vector<int> in_vec = {
     4,3,5,4,3,3,6,7 };
	
	for (int i = 0; i < S; i++)
	{
    
		while(!que_idx.empty() && in_vec[que_idx.back()] <= in_vec[i])
			que_idx.pop_back();
		que_idx.push_back(i);		
	}

	res.push_back(in_vec[que_idx.front()]);

	for (int j = 1, k = S; j < in_vec.size() && k < in_vec.size(); j++, k++)
	{
    
		if (j-1 == que_idx.front())
		{
    
			que_idx.pop_front();
		}
		while (!que_idx.empty() && in_vec[que_idx.back()] <= in_vec[k])
			que_idx.pop_back();
		que_idx.push_back(k);
		res.push_back(in_vec[que_idx.front()]);
	}
	for (int m = 0; m < res.size(); m++)
	{
    
		cout << res[m] << " ";
	}
	return 0;
}