lintcode 滑动窗口的最大值(双端队列)

题目链接：http://www.lintcode.com/zh-cn/problem/sliding-window-maximum/#

滑动窗口的最大值

给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

样例

给出数组 [1,2,7,7,8], 滑动窗口大小为 k = 3. 返回 [7,7,8].

解释：

最开始，窗口的状态如下：

[|1, 2 ,7| ,7 , 8], 最大值为 7;

然后窗口向右移动一位：

[1, |2, 7, 7|, 8], 最大值为 7;

最后窗口再向右移动一位：

[1, 2, |7, 7, 8|], 最大值为 8.

挑战

O(n)时间，O(k)的额外空间

解决方案：

　　关于此题的理解， 为什么双端队列中插如的是数的索引，而不是数的本身？
因为如果是数的本身，我们就无法判断窗口在移动的时候窗口里的数时候被移出窗口！

　　如果插入的是数的索引，那么该如何找出窗口中的最大值呢？
　　我们用双端队列维护一个队首为大数索引，队尾为小树索引的队列， 如果将要插入索引对应的数大于队列末尾所对应的数，
那么队列的末尾元素就被移出(此时将要插入的数和队尾元素对应的数一定在同一窗口，既然将要插入索引对应的数大于队列末尾所对应的数，那么队列末尾所对应的数一定没有机会成为窗口中的最大值);如果队列中队首值(窗口中元素最大数的索引) 不在新窗口的范围里了，那么也要移出队首元素。

vector<int> maxSlidingWindow(vector<int> &nums, int k) {deque<int> dq;vector<int> ret;int len = nums.size();for(int i=0; i<k; ++i){while(!dq.empty() && nums[i]>nums[dq.back()])dq.pop_back();dq.push_back(i);}for(int i=k; i<len; ++i){ret.push_back(nums[dq.front()]);while(!dq.empty() && nums[i]>nums[dq.back()])dq.pop_back();if(!dq.empty() && dq.front() <= i-k)dq.pop_front();dq.push_back(i);}ret.push_back(nums[dq.front()]);return ret; }

 

 

总结

以上是生活随笔为你收集整理的lintcode 滑动窗口的最大值(双端队列)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。