单调队列笔记

发表于 更新于 分类于 ， 本文字数： 706 阅读时长 ≈ 5 分钟
单调队列，一种特殊的队列，是的，它具有单调性

简介

单调队列是一种特殊的队列，它里面的元素都是按照单调递减或单调递增的顺序进行排列。

它和单调栈一样，只能解决某些特定的问题。

单调队列能够维护一个滑动窗口区间内的最值(最大值或者最小值)。

代码模版：

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
import collections


def window_max(nums,k):
    '''在一个数组中，找出所有位置的滑动窗口的最大值
    
    Args:
        nums: 一维数组
        k: 滑动窗口的大小

    Returns:
        返回一个数组，统计滑动窗口的最大值
    '''
    n = len(nums)
    mono_queue = collections.deque()
    ans = []
    for i in range(k-1):
        while mono_queue and nums[mono_queue[-1]] < nums[i]:
            mono_queue.pop()
        mono_queue.append(i)
    
    for i in range(k-1,n):
        while mono_queue and nums[mono_queue[-1]] < nums[i]:
            # 维护单调队列中头部为最大值
            mono_queue.pop()
        mono_queue.append(i)
        while mono_queue and mono_queue[0] <= i-k:
            # 此时最大值已经不在滑动窗口内了，需要移除掉
            mono_queue.popleft()
        ans.append(nums[mono_queue[0]])
    return ans

参考资料

  1. 算法学习笔记(66): 单调队列