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;
}
时间: 2016-04-28

lintcode 滑动窗口的最大值(双端队列)的相关文章

lintcode二叉树的锯齿形层次遍历 (双端队列)

v题目链接: http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/ v二叉树的锯齿形层次遍历  给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)  v样例 给出一棵二叉树 {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 返回其锯齿形的层次遍历为: [ [3], [20,9], [15,7] ] v思路: 我们用双端

剑指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,

双端队列算法练习题

话说大学的时候老师说妹子比工作重要~,工作可以再换,妹子这个...所以...这两个月也就 一直忙着Fall in love,嗨,慢慢调整心态吧,这篇就选一个简单的数据结构聊一聊,话说有很多数据 结构都在玩组合拳,比如说:块状链表,块状数组,当然还有本篇的双端队列,是的,它就是栈和队列 的组合体. 一:概念 我们知道普通队列是限制级的一端进,另一端出的FIFO形式,栈 是一端进出的LIFO形式,而双端队列就没有这样的限制级,也就是我们可以在队列两端进行插入或者删 除操作. 二:编码 1:定义结构体

【C/C++学院】0828-STL入门与简介/STL容器概念/容器迭代器仿函数算法STL概念例子/栈队列双端队列优先队列/数据结构堆的概念/红黑树容器

STL入门与简介 #include<iostream> #include <vector>//容器 #include<array>//数组 #include <algorithm>//算法 using namespace std; //实现一个类模板,专门实现打印的功能 template<class T> //类模板实现了方法 class myvectorprint { public: void operator ()(const T &

经典算法题每日演练——第十九题 双端队列

     话说大学的时候老师说妹子比工作重要~,工作可以再换,妹子这个...所以...这两个月也就一直忙着Fall in love,嗨,慢慢调整心态吧, 这篇就选一个简单的数据结构聊一聊,话说有很多数据结构都在玩组合拳,比如说:块状链表,块状数组,当然还有本篇的双端队列,是的,它就是 栈和队列的组合体. 一:概念      我们知道普通队列是限制级的一端进,另一端出的FIFO形式,栈是一端进出的LIFO形式,而双端队列就没有这样的限制级,也就是我们可以在 队列两端进行插入或者删除操作. 二:编码

详解Python的collections模块中的deque双端队列结构_python

deque 是 double-ended queue的缩写,类似于 list,不过提供了在两端插入和删除的操作. appendleft 在列表左侧插入 popleft 弹出列表左侧的值 extendleft 在左侧扩展 例如: queue = deque() # append values to wait for processing queue.appendleft("first") queue.appendleft("second") queue.appendl

Python实现的数据结构与算法之双端队列详解_python

本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe

Lua编程示例(三):稀疏表、双端队列、格式化输出、表和循环表的格式化输出_Lua

a={} for i=1,10 do a[i]={} for j=0,10 do if(i%2==0) then a[i][j]=0 end end end print(a[9][10]) print(a[10][10]) print() --双端队列 List={} function List.new() return {first = 0,last = -1} end function List.pushleft(list,value) local first= list.first-1 l

STL队列 之FIFO队列(queue)、优先队列(priority_queue)、双端队列(deque)

1.FIFO队列     std::queue就是普通意思上的FIFO队列在STL中的模版. 1.1主要的方法有: (1)T front():访问队列的对头元素,并不删除对头元素 (2)T back():访问队列的末尾元素,并不删除末尾元素 (3)void pop():删除对头元素. (4)void push(T):元素入队 1.2代码实例 1 #include <iostream> 2 #include <queue> 3 using namespace std; 4 int m