双端队列

class deque {
? ?// 在队头插入元素 n
? ?void push_front(int n);
? ?// 在队尾插入元素 n
? ?void push_back(int n);
? ?// 在队头删除元素
? ?void pop_front();
? ?// 在队尾删除元素
? ?void pop_back();
? ?// 返回队头元素
? ?int front();
? ?// 返回队尾元素
? ?int back();
}如果用链表实现,

这些操作的复杂度都是 O(1)

Python3中的调用

import collections
d = collections.deque()

append(往右边添加一个元素)

import collections
d = collections.deque()
d.append(1)
d.append(2)
print(d)

输出：deque([1, 2])

appendleft（往左边添加一个元素）

clear(清空队列)
copy(浅拷贝)
count(返回指定元素的出现次数)
extend(从队列右边扩展一个列表的元素)
extendleft(从队列左边扩展一个列表的元素)
index（查找某个元素的索引位置）
insert（在指定位置插入元素）

pop（获取最右边一个元素，并在队列中删除）

popleft（获取最左边一个元素，并在队列中删除）

remove（删除指定元素）
?简记:对右端的操作与列表list相同
如果要getleft和getright
直接用d[0],d[-1]
判断是否为空:
if d 表示如果d不为空
if not d 表示如果d为空

从这一点可以看出该对象容器继承自list,包含list的所有功能

单调递减队列

class MonotonicQueue {
? ?// 在队尾添加元素 n
? ?void push(int n);
? ?// 返回当前队列中的最大值
? ?int max();
? ?// 队头元素如果是 n，删除它
? ?void pop(int n);
}

它的操作就很少了,如果用deque来实现
其中的int max()就是deque.left() 即python中deque[0],因为是单调的
为了保持单调性 push改写为先删除右端所有比插入数值更小的数

class MonotonicQueue {
private:
    deque<int> data;
public:
    void push(int n) {
        while (!data.empty() && data.back() < n) 
            data.pop_back();
        data.push_back(n);
    }
};

而本题中不是要直接去调单调队列的包,而是以双端队列为基础,把单调队列的实现思想用进来

看一下这道题

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

?滑动窗口的位置 ? ? ? ? ? ? ? ?最大值

--------------- ? ? ? ? ? ? ? -----

[1 ?3 ?-1] -3 ?5 ?3 ?6 ?7 ? ? ? 3
1 [3 ?-1 ?-3] 5 ?3 ?6 ?7 ? ? ? 3
1 ?3 [-1 ?-3 ?5] 3 ?6 ?7 ? ? ? 5
1 ?3 ?-1 [-3 ?5 ?3] 6 ?7 ? ? ? 5
1 ?3 ?-1 ?-3 [5 ?3 ?6] 7 ? ? ? 6
1 ?3 ?-1 ?-3 ?5 [3 ?6 ?7] ? ? ?7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：

你能在线性时间复杂度内解决此题吗？

Python题解(通过leetcode)

先看东北程序员视频

import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums: return []
        d = collections.deque()
        res = []
        for i in range(len(nums)):
            # 如果队头正好就离开了滑动窗口,pop它
            if d and d[0] == i - k:
                d.popleft()
            # 单调队列.push()
            while d and nums[d[-1]] < nums[i]:
                d.pop()
            d.append(i)
            if i + 1 >= k: 
                # 窗口开始滑动
                res.append(nums[d[0]])
        return res

时间复杂度

时间复杂度按道理来说是O(n),如果在c++中
但python先天劣势,deque继承自list,list底层是数组,所以操作做不到O(n),最坏情况的时间复杂度是O(n2)
即便如此,我们需要掌握的还是这个算法,以便以后用其他语言也能做出来
空间复杂度最坏情况O(n)

抄的题解

作者：labuladong
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/

239. 滑动窗口最大值/双端队列/单调队列

原文：https://www.cnblogs.com/Akarinnnn/p/12080051.html