剑指offer：滑动窗口的最大值65

https://blog.****.net/gogokongyin/article/details/51788176

题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5}。
滑动窗口这个概念在写过网络编程的人都应该是不陌生，主要是用来进行流控的。利用接收方剩下的缓冲数据区的大小来控制发送端的发送速度，避免发送端发送过快，导致网络拥塞及其他故障问题。
方案一：蛮力法，顺序分块扫描。例如在上例中，我们进行不断的分组和查找，3个一组，这样最终会找出其最大值。但是其时间复杂度为O(NK)。N为滑动窗口的数量，K为滑动窗口的大小。
方案二：栈实现。滑动窗口我们知道是先进先出的数据处理顺序，很明显是一个队列。在[21]中我们知道我们可以用栈来实现一个O(1)时间复杂度来得到最大值，在[6]中我们也讲到过用两个栈来实现一个队列，这样我们可以用两个栈来实现队列，同时也可以用O(1)的时间来得到栈中的最大值。所以总的时间复杂度就降低到了O(N).
方案三：双端队列实现。由于方案二中实现的步骤比较复杂，所以我们换了一种思路，在取得最大值的过程中，我们并不把每个数值都存入队列，而只是把有可能成为最大值的数据存入到两端开口的队列(deque)中，上面的输入为例，其求解过程如下：

1、思路

我们可以使用一个双端队列deque。

我们可以用STL中的deque来实现，接下来我们以数组{2,3,4,2,6,2,5,1}为例，来细说整体思路。

数组的第一个数字是2，把它存入队列中。第二个数字是3，比2大，所以2不可能是滑动窗口中的最大值，因此把2从队列里删除，再把3存入队列中。第三个数字是4，比3大，同样的删3存4。此时滑动窗口中已经有3个数字，而它的最大值4位于队列的头部。

第四个数字2比4小，但是当4滑出之后它还是有可能成为最大值的，所以我们把2存入队列的尾部。下一个数字是6，比4和2都大，删4和2，存6。就这样依次进行，最大值永远位于队列的头部。

但是我们怎样判断滑动窗口是否包括一个数字？应该在队列里存入数字在数组里的下标，而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者相等于滑动窗口大小时，这个数字已经从窗口中滑出，可以从队列中删除。

剑指offer：滑动窗口的最大值65

*  单调队列，O(n)
 *  deque s中存储的是num的下标
 *
 *  题目：滑动窗口的最大值
 *
 *  思路：滑动窗口应当是队列，但为了得到滑动窗口的最大值，队列序可以从两端删除元素，因此使用双端队列。
 *
 *  原则：
 *  对新来的元素k，将其与双端队列中的元素相比较
 *  1.  前面比k小的，直接移出队列（因为不再可能成为后面滑动窗口的最大值了!）,
 *  2.  前面比k大的X，比较两者下标，判断X是否已不在窗口之内，不在了，直接移出队列
 *  队列的第一个元素是滑动窗口中的最大值
 *  */

class Solution
{
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int>     res;
        deque<int>      index;
        for(unsigned int i = 0; i < num.size( ); i++)
        {
            cout <<"size["<<index.size( ) <<"] : ";
            copy(index.begin( ), index.end( ), ostream_iterator<int>(cout," "));
            cout <<endl;

            /*  从后面依次弹出队列中比当前num值小的元素，
             *  同时也能保证队列首元素为当前窗口最大值下标  */
            while(index.size( ) != 0 && num[index.back( )] <= num[i])
            {
                index.pop_back( );
            }
            /*  当前窗口移出队首元素所在的位置
                即队首元素坐标对应的num不在窗口中，需要弹出  */
            while(index.size() && i - index.front( ) + 1 > size)
            {
                index.pop_front( );
            }

            /*  把每次滑动的num下标加入队列  */
            index.push_back(i);

            /*  当滑动窗口首地址i大于等于size时才开始写入窗口最大值  */
            if(size != 0 && i + 1 >= size)
            {
                res.push_back(num[index.front( )]);
            }
        }
        return res;
    }
};

简洁版本：

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> q;
        for(unsigned int i=0;i<num.size();++i){
            while(q.size()&&num[q.back()]<=num[i]) //弹出比K值小的队尾弹出
                q.pop_back();
            while(q.size() && i-q.front()+1>size)//弹出距离超过size的 ，队首弹出
                q.pop_front();
            q.push_back(i);
            if(size&&i+1>=size) 
          //当i超过size值，每一轮必入res一个值，且是 q的队首，因为队首每次都是最大值
                res.push_back(num[q.front()]);
        }
        return res;
    }
};

剑指offer：滑动窗口的最大值65

1、思路

相关推荐