算法笔记之双向队列

双向队列是一种插入和删除都可以在两端进行的数据结构，有点类似队列和栈的结合。

在实际场景中应用不是很多，但也可以解决一些问题。

LeetCode 239. 滑动窗口最大值

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

要求，返回滑动窗口中的最大值。希望在线性时间复杂度解决问题。

示例：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解题思路：使用双向队列，分为如下步骤：

1. 处理前 k 个元素，初始化双向队列。
2. 遍历整个数组。在每一步需进行操作：a)只保留当前滑动窗口中有的元素的索引。b)移除比当前元素小的所有元素，它们不可能是最大的。
3. 将当前元素添加到双向队列中。
4. 将 deque[0] 添加到输出中。
5. 返回输出数组。

Python代码：

def maxSlidingWindow(self, nums, k):
    '''
    nums: 给定的数组
    k: 窗口大小，小于数组长度
    '''
    import collections
    deq = collections.deque()
    # 移动窗口
    def move(i):
        # 删除不在窗口的元素
        if deq and deq[0] < i - k + 1:
            deq.popleft()
        
        # 从右侧删除比当前元素小的元素
        while deq and nums[deq[-1]] <= nums[i]:
            deq.pop()
        deq.append(i)
    result = []
    # 初始k个元素
    for i in range(k):
        move(i)
    result.append(nums[deq[0]])
    # 移动窗口
    for i in range(k, len(nums)):
        move(i)
        result.append(nums[deq[0]])
    return result