剑指offer64：滑动窗口的最大值

1 题目描述

　　给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[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,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

2 思路和方法

　　（1）使用int max_number =*max_element(num.begin()+i,num.begin()+size+i);语句找到最大值，int count = num.size()-size+1;　　vector<int> result; 　　result. push_back(max_number)。

　　（2）用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次。a.判断当前最大值是否失效，即不在滑动窗口内；b.新增加的值从队尾开始比较，把所有比他小的值丢掉。

3 C++核心

（1）

 class Solution {

 public:

     vector<int> maxInWindows(const vector<int>& num, unsigned int size)

     {

         int count = num.size()-size+;

         vector<int> result;

         if(size== || num.size()==){

             return result;

         }

         for(int i =;i<count;i++){

             int max_number = *max_element(num.begin()+i,num.begin()+size+i);

             result.push_back(max_number);

         }

         return result;

     }

 };

（2）

 class Solution {

 public:

     vector<int> maxInWindows(const vector<int>& num, unsigned int size)

     {

         vector<int> resu;

         if (num.size() >= size && size >= ) {

             deque<int> numDeque;

             //首先把前size个数按照规则压入双向队列

             for (int i = ; i != size; i++) {

                 while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {

                     numDeque.pop_back();    //后面加入的数据大于队列中的数据时，队列中的数据依次弹出

                 }

                 numDeque.push_back(i);

             }

             //压入第一个最大值

             //滑动窗口的最大值总是位于双向队列的头部

             resu.push_back(num[numDeque.front()]);

             for (int i = size; i != num.size(); i++) {

                 //首先按照规则压入新的值

                 while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {

                     numDeque.pop_back();    //后面加入的数据大于队列中的数据时，队列中的数据依次弹出

                 }

                 //并且删除旧值，即滑出了窗口的值

                 if (!numDeque.empty() && numDeque.front() <= static_cast<int>(i - size)) {

                     numDeque.pop_front();

                 }

                 numDeque.push_back(i);

                 resu.push_back(num[numDeque.front()]);

             }

         }

         return resu;

     }

 };

4 C++完整代码

 #include <iostream>

 #include <vector>

 #include <deque>

 using namespace std;

 vector<int> maxInWindows(const vector<int>& num, unsigned int size);

 int main() {

     vector<int> data{ , , , , , , ,  };

     vector<int> resu = maxInWindows(data, );

     for (auto a : resu) {

         cout << a << endl;

     }

     system("pause");

     return ;

 }

 vector<int> maxInWindows(const vector<int>& num, unsigned int size) {

     vector<int> resu;

     if (num.size() >= size && size >= ) {

         deque<int> numDeque;

         //首先把前size个数按照规则压入双向队列

         for (int i = ; i != size; i++) {

             while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {

                 numDeque.pop_back();

             }

             numDeque.push_back(i);

         }

         //压入第一个最大值

         //滑动窗口的最大值总是位于双向队列的头部

         resu.push_back(num[numDeque.front()]);

         for (int i = size; i != num.size(); i++) {

             //首先按照规则压入新的值

             while (!numDeque.empty() && num[i] >= num[numDeque.back()]) {

                 numDeque.pop_back();

             }

             //并且删除旧值，即滑出了窗口的值

             if (!numDeque.empty() && numDeque.front() <= static_cast<int>(i - size)) {

                 numDeque.pop_front();

             }

             numDeque.push_back(i);

             resu.push_back(num[numDeque.front()]);

         }

     }

     return resu;

 }

参考资料

https://blog.csdn.net/u012477435/article/details/83351659#_1782（1）

https://blog.csdn.net/qq_43502142/article/details/87894236（图解）

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（核心代码，完整代码）

https://blog.csdn.net/qq_40788630/article/details/79662812（队列相关知识点）

https://blog.csdn.net/lee371042/article/details/81135007（队列与优先队列【有序】的总结）

巴特西