【数据结构与算法】双端队列 deque

发表于 更新于 分类于 阅读次数：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

参考《程序员面试指南：IT名企算法于数据结构题目最优解（第2版）》

双端队列deque

普通的队列是先入先出FIFO（First In First Out），只能从队尾添加元素，从队首弹出元素。而双端队列则是从队尾添加元素，但是既可以从队首弹出元素，和普通的队列一样，也可以和栈一样从队尾弹出元素，所以叫双端队列deque（double-ended queue），它同时具备队列（FIFO）和栈（LIFO）的特性。

生成窗口最大值数组

题目描述

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。请实现一个函数。
● 输入：整型数组arr，窗口大小为w。
● 输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。

示例：
输入：arr = [4，3，5，4，3，3，6，7], w = 3
输出：res = [5，5，5，4，6，7]

暴力解法

时间复杂度为$\mathcal{O}(N\times w)$，遍历arr，每次统计w窗口中的最大值即可。

双端队列解法

时间复杂度为$\mathcal{O}(N)$。
大致思路是维护一个从队首到队尾单调递减的双端队列qmax，其中存放着arr中的下标，还有一个res数组。
遍历到arr[i]时qmax的更新规则为：

  1. 如果qmax为空，则直接将i放入队尾；
  2. 如果qmax不为空，则需要判断队尾元素j对应arr[j]与当前元素的大小：

1). 如果arr[j] <= arr[i]，则弹出j，继续更新规则；
2). 如果arr[j] > arr[i]，则直接将i添加进队尾。
3. 如果qmax[0] == i - w，则说明队首元素不再位于w窗口内，则弹出队首元素。
4. 如果i >= w - 1，则向res添加arr[qmax[0]]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
arr = [4, 3, 5, 4, 3, 3, 6, 7]
w = 3

n = len(arr)
# Python中用list模拟deque
deque, res = [], []

for i in range(n):
    if not deque:
        deque.append(i)
    else:
        while deque and arr[i] >= arr[deque[-1]]:
            deque.pop()
        deque.append(i)

        if deque[0] == i - w:
            deque.pop(0)

    if i >= w - 1:
        res.append(arr[deque[0]])

print(res)
# [5, 5, 5, 4, 6, 7]

最大值减去最小值差值小于等于num的子数组数量

题目描述

给定数组arr和整数num，返回一共有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num

示例：
输入：arr = [4，3，5，4，3，3，6，7], num = 1
输出：ans = 14

暴力解法

时间复杂度为$\mathcal{O}(N^3)$，首先arr一共有$\mathcal{O}(N^2)$个子数组，然后找出每个子数组的最小值和最大值，再判断是否满足条件$\mathcal{O}(N)$。

双端队列解法

时间复杂度为$\mathcal{O}(N)$。
大致思路是维护两个双端队列qmax和qmin，分别是从队首到队尾递减和递增，qmax队首表示当前子数组arr[i..j]最大值，qmin队首表示当前子数组arr[i..j]最小值，i和j都是从0开始的两个指针，i表示子数组左边界，j表示子数组右边界，ans代表最终答案，初始为0。

  1. 遍历到arr[j]时，更新qmax和qmin，更新规则和上一题一样；
  2. 重复第一步直到arr[qmax[0]] - arr[qmin[0]] > num，则j指针暂停移动，ans += j - i（j - i表示严格以i起始的满足条件的子数组数量），然后如判断qmax和qmin的队首元素是否为i，如果是则弹出i，之后将i指针向后移动一位，重复一二步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
arr = [4, 3, 5, 4, 3, 3, 6, 7]
num = 1

n = len(arr)
qmax, qmin = [], []
ans = 0
i, j = 0, 0

while i < n:
    while j < n:
        while qmax and arr[j] >= arr[qmax[-1]]:
            qmax.pop()
        qmax.append(j)
        while qmin and arr[j] <= arr[qmin[-1]]:
            qmin.pop()
        qmin.append(j)

        if arr[qmax[0]] - arr[qmin[0]] > num:
            break
        j += 1

    ans += j - i

    if qmax[0] == i:
        qmax.pop(0)
    if qmin[0] == i:
        qmin.pop(0)
    i += 1

print(ans)
"""
arr = [4, 3, 5, 4, 3, 3, 6, 7]
num = 1
ans = 14

arr = [4, 3, 5, 4, 3, 3, 6, 7]
num = 2
ans = 24
"""