Given an array and the size of the sliding window, find the maximum value in all sliding windows. For example, if the input array {2,3,4,2,6,2,5,1} and the size of the sliding window are 3, then there are six sliding windows, their maximum values are {4,4,6,6,5}; for the array {2,3,4,2,6,2,5,1}, there are sliding windows. The following six: {[2,3,4], 2,6,2,5,1}, {2,[3,4,2], 6,2,5,1}, {2,3,[4,2,6], 2,5,1}, {2,3,4,[2,6], 5,1}, {2,3,4,[2,6,2], 5,1}, {2,3,4,2,[6,2], 5], 1}, {2,3,4,2,[6], 1}, {2,3,4,6,{2,5,6,[2,5,1].

2 Thoughts and Methods

(1) Use int max_number=*max_element (num.begin()+i, num.begin()+size+i); statement to find the maximum value, int count = num.size()-size+1; vector < int > result; result. push_back(max_number).

(2) a double-ended queue is used. The maximum value of the current window is saved at the first position of the queue when the window slides once. a. Judging whether the current maximum is invalid, that is, not in the sliding window; b. Comparing the newly added values from the end of the team, all the values smaller than him are discarded.

　　

3 C++ core

(1)

 1 class Solution {
 2 public:
 3     vector<int> maxInWindows(const vector<int>& num, unsigned int size)
 4     {
 5         int count = num.size()-size+1;
 6         vector<int> result;
 7         if(size==0 || num.size()==0){
 8             return result;
 9         }
10         for(int i =0;i<count;i++){
11             int max_number = *max_element(num.begin()+i,num.begin()+size+i);
12             result.push_back(max_number);
13         }
14         return result;
15     }
16 };

(2)

 1 class Solution {
 2 public:
 3     vector<int> maxInWindows(const vector<int>& num, unsigned int size)
 4     {
 5         vector<int> resu;
 6         if (num.size() >= size && size >= 1) {
 7             deque<int> numDeque;
 8             //First of all, the former size Number pressed into two-way queue according to rules
 9             for (int i = 0; i != size; i++) {
10                 while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
11                     numDeque.pop_back();    //When the data added later is larger than the data in the queue, the data in the queue pops up in turn.
12                 }
13                 numDeque.push_back(i);
14             }
15             //Press in the first maximum
16             //The maximum value of the sliding window always lies at the head of the bidirectional queue
17             resu.push_back(num[numDeque.front()]);
18             for (int i = size; i != num.size(); i++) {
19                 //First press the new values according to the rules
20                 while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
21                     numDeque.pop_back();    //When the data added later is larger than the data in the queue, the data in the queue pops up in turn.
22                 }
23                 //And delete the old value, that is, the value of the window slides out.
24                 if (!numDeque.empty() && numDeque.front() <= static_cast<int>(i - size)) {
25                     numDeque.pop_front();
26                 }
27                 numDeque.push_back(i);
28                 resu.push_back(num[numDeque.front()]);
29             }
30         }
31         return resu;
32     }
33 };

4 C++ Complete Code

 1 #include <iostream>
 2 #include <vector>
 3 #include <deque>
 4 using namespace std;
 5 vector<int> maxInWindows(const vector<int>& num, unsigned int size);
 6 int main() {
 7     vector<int> data{ 2, 3, 4, 2, 6, 2, 5, 1 };
 8     vector<int> resu = maxInWindows(data, 3);
 9     for (auto a : resu) {
10         cout << a << endl;
11     }
12     system("pause");
13     return 0;
14 }
15 vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
16     vector<int> resu;
17     if (num.size() >= size && size >= 1) {
18         deque<int> numDeque;
19         //First of all, the former size Number pressed into two-way queue according to rules
20         for (int i = 0; i != size; i++) {
21             while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
22                 numDeque.pop_back();
23             }
24             numDeque.push_back(i);
25         }
26         //Press in the first maximum
27         //The maximum value of the sliding window always lies at the head of the bidirectional queue
28         resu.push_back(num[numDeque.front()]);
29         for (int i = size; i != num.size(); i++) {
30             //First press the new values according to the rules
31             while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {
32                 numDeque.pop_back();
33             }
34             //And delete the old value, that is, the value of the window slides out.
35             if (!numDeque.empty() && numDeque.front() <= static_cast<int>(i - size)) {
36                 numDeque.pop_front();
37             }
38             numDeque.push_back(i);
39             resu.push_back(num[numDeque.front()]);
40         }
41     }
42     return resu;
43 }

Reference material

https://blog.csdn.net/u012477435/article/details/83351659#_1782(1)

https://blog.csdn.net/qq_43502142/article/details/87894236 (illustration)

https://blog.csdn.net/qq_37466121/article/details/88410390，https://blog.csdn.net/qq_43502142/article/details/87894236，https://blog.csdn.net/zjwreal/article/details/89295109(2)

https://blog.csdn.net/m0_37950361/article/details/82153147 (core code, complete code)

https://blog.csdn.net/qq_40788630/article/details/79662812 (queue-related knowledge points)

https://blog.csdn.net/lee371042/article/details/81135007 (summary of queues and priority queues)