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

简介:

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

v滑动窗口的最大值

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

v样例

给出数组 [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.

v挑战

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

v解决方案:

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

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


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;
}


目录
相关文章
|
20天前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
28 1
|
6月前
|
存储
每日一题——滑动窗口的最大值
每日一题——滑动窗口的最大值
|
6月前
|
算法 测试技术 C#
【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数
【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数
|
6月前
|
算法 测试技术 C#
【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值
【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值
|
6月前
剑指 Offer 59 - I:滑动窗口的最大值
剑指 Offer 59 - I:滑动窗口的最大值
41 0
|
6月前
|
存储 Java C++
leetcode-239:滑动窗口最大值
leetcode-239:滑动窗口最大值
54 0
|
11月前
|
C++ 索引
LeetCode239|剑指 Offer 59 - I. 滑动窗口的最大值
前言 看到滑动窗口以及示例,很容易被思维局限了,然后呢就开始打框架,用一个for循环,i-i+3这样的范围一直移动,但是每次都要比较这3个值的大小,如何比较呢?用类似之前T155的栈一样比较吧。但是存在一个问题,有些值就重复2-3次,似乎没有这个必要。
27 0
滑动窗口(单调队列)
滑动窗口(单调队列)
44 0
|
存储
剑指offer 67. 滑动窗口的最大值
剑指offer 67. 滑动窗口的最大值
52 0
|
算法 C++ Python
每日算法系列【LeetCode 239】滑动窗口最大值
每日算法系列【LeetCode 239】滑动窗口最大值
115 0