Sliding Window

leetcode 239.Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Example 3:

Input: nums = [1,-1], k = 1
Output: [1,-1]

Example 4:

Input: nums = [9,11], k = 2
Output: [11]

Example 5:

Input: nums = [4,-2], k = 2
Output: [4]

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/sliding-window-maximum

This problem can be solved by double ended monotone queue ：
Because in the process of sliding the window forward , We will find that , Every time the window slides forward , To add a number, you should also reduce a number , Add a new element , If this new element is larger than some numbers in the window , So these numbers are smaller than the new elements , Until it was eliminated, there was no chance to show up .
eg: Sequence [10,7,5],6,4,3
After the window slides forward , The new data 6 Than 5 Be big , that , This 5 It cannot be the largest number until it is eliminated , Because there is a 6 always Suppress With it .
10,[7,5,6],4,3 ---------------------- Max = 7
10,7,[5,6,4],3 ---------------------- Max = 6
10,7,5,[6,4,3] ---------------------- Max = 6

Then we can go through the sequence , When pressing in a new data , Put all the numbers smaller than it before , Delete all , Only keep numbers larger than it , Then the final sequence must be a monotonically decreasing sequence , This is the monotonic queue .
Then why double ended queues , Because new data is being added to the queue , And deleting data smaller than the new data is realized at the end of the team , But to get the value of the largest data after each window move , You need the team leader element , use queue.front() To get , And the window slides forward , You have to delete the element at the left end of the sliding window , So we have to use a two terminal monotonic queue .

Code ：

class Solution {
    
private:
    deque<int> data; //double-ended queue
public:
    void push(int DATA)
    {
    
        // Add elements at the end of the team , Delete the previous elements smaller than the new elements 
        while(!data.empty() && data.back() < DATA){
    
            data.pop_back();
        }
        data.push_back(DATA);
    } // Form a monotonically decreasing sequence 

    int max(){
     return data.front(); }

    void pop(int DATA){
    
        /* Slide the window forward one bit , Add one digit to the right , You have to subtract one digit from the left , But if it has been flattened ,  That is to say, the leftmost number in the queue no longer exists , You don't have to delete , Otherwise, you have to delete this number */
        if(!data.empty() && data.front() == DATA){
    
            data.pop_front();
        }
    };

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        Solution window;
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
    
            if(i < k - 1){
     // Fill the front of the window first K - 1
                window.push(nums[i]);
            }
            else{
     // The window slides forward 
                window.push(nums[i]);
                res.push_back(window.max());
                window.pop(nums[i - k + 1]); // Refers to the leftmost number of the sliding window , Check whether it is in the queue , Delete if any 
            }
        }
        return res;
    }
};

---

Luogu P1886 The sliding window /【 Templates 】 A monotonous queue

Luo Gu also has this problem , It's just that there's more to find the minimum . The idea is the same .

Input #1

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

Output #1

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

link ：https://www.luogu.com.cn/problem/P1886

#include<iostream>
#include<deque>
#include<cstdio>
#include<vector>
using namespace std;
long long int res[1000001] = {
     0 }, res1[1000001] = {
     0 };
void push(deque<long long int>& line, long long int data, int flag)
{
    
	if (flag == 1){
    
		while (!line.empty() && line.back() < data)
			line.pop_back();
		line.push_back(data);
	}
	else{
    
		while (!line.empty() && line.back() > data)
			line.pop_back();
		line.push_back(data);
	}
}

void pop_data(deque<long long int>& line, long long int data)
{
    
	if (!line.empty() && line.front() == data)
		line.pop_front();
}

int main(){
    
	deque<long long int> q, qq;
	int i, n, k, len1 = 0, len2 = 0;
	long long int xx;
	vector<long long int> nums;
	cin >> n >> k;
	for (i = 0; i<n; i++){
    
		cin >> xx;
		nums.push_back(xx);
	}
	for (i = 0; i < n; i++){
    
		if (i < k - 1){
    
			push(q, nums[i], 1);
			push(qq, nums[i], 2);
		}
		else{
    
			push(q, nums[i], 1);
			push(qq, nums[i], 2);
			res[len1++] = q.front();
			res1[len2++] = qq.front();
			pop_data(q, nums[i - k + 1]);
			pop_data(qq, nums[i - k + 1]);
		}
	}
	for (i = 0; i<len2; i++)
		printf("%lld ", res1[i]);
	printf("\n");
	for (i = 0; i<len1; i++)
		printf("%lld ", res[i]);
	return 0;
}