剑指offer 面试题. 滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

解答：

用一个双端队列模拟当前的窗口。

首先队列维护非递增序，因为如果队列中有增序的数字，比如a，b，c为当前队列，有a<c。那么显然当前窗口中a一定不是最大值，并且a也不可能是之后某个窗口的最大值（因为c的索引在a之后，a先滑出窗口）。故a也就没有存储的必要。那么递减的数字为什么要存储呢？比如数组3，2，1，窗口大小k=2。那么起初的窗口为[3,2]，队列为3，2。窗口右移一位，3被移出窗口，此时队列剩下2，由于1比2小故push，则队列中此时为2，1。那么如果之前不保存元素2，后面的窗口如果需要用到2（此例就用到了），便会出错。

模拟一个栗子以加深对滑动窗口的理解：

数组{2,3,4,2,6,2,5,1}，窗口长度k=3

窗口[2,3,4]，队列[4]，实际是push2，pop2，push3，pop3，push4。

窗口[3,4,2]，2<=4，所以push2，得队列[4,2]

窗口[4,2,6]，6>2，pop2，此时队列[4]，6>4，pop4，push6，得队列[6]

窗口[2,6,2]，2<=6，所以push2，得队列[6,2]

窗口[6,2,5]，5>2，pop2，此时队列[6]，5<=6，push5，得队列[6,5]

窗口[2,5,1]，由于6等于移出队列的元素，pop_front(6)，此时队列[5]，1<=5，push1，得队列[5,1]

每一步得到的队列的队首就是当前窗口的最大值，分别为4，4，6，6，6，5

代码：

队列存元素：

 class Solution {

 public:

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

     {

         if(size== or num.size()<size){return {};}

         int k=size;

         deque<int> que;

         vector<int> res;

         int le=,ri=;

         while(ri<num.size()){

             while(ri-le<k){

                 while(not que.empty() and que.back()<num[ri]){

                     que.pop_back();

                 }

                 que.push_back(num[ri++]);//存元素

             }

             res.push_back(que.front());

             le++;

             if(que.front()==num[le-]){

                 que.pop_front();

             }

         }

         return res;

     }

 };

队列中保存数组索引也可以：

 class Solution {

 public:

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

     {

         if(num.size()<size){return {};}

         int k=size;

         deque<int> que;

         vector<int> res;

         int le=,ri=;

         while(ri<num.size()){

             while(ri-le<k){

                 while(not que.empty() and num[que.back()]<num[ri]){

                     que.pop_back();

                 }

                 que.push_back(ri++);//存索引

             }

             res.push_back(num[que.front()]);

             le++;

             if(que.front()==le-){

                 que.pop_front();

             }

         }

         return res;

     }

 };

巴特西

剑指offer 面试题. 滑动窗口的最大值

题目描述

解答：

代码：

最新文章

热门文章