python双端队列deque应用——滑动窗口最大值

刷LeetCode3. 无重复字符的最长子串的时候，得知要用到滑动窗口，然后得知滑动窗口的入门应用——用双端队列deque解决滑动窗口最大值问题。

滑动窗口最大值问题（参考https://blog.csdn.net/summer2day/article/details/89853737?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165094533816782248529327%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=165094533816782248529327&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allbaidu_landing_v2~default-4-89853737.142^v9control,157^v4control&utm_term=LeetCode+%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3&spm=1018.2226.3001.4187）：

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

滑动窗口最大值问题需用到的Python中的deque相关知识：

# 调用：
from collections import deque
dq = deque(maxlen=k)# 表示创建一个长度为k的双端队列
# 取队首元素：
dq[0]
# 取队尾元素：
dq[-1]
# 移除并返回队尾元素：
dq.pop()
# 在队尾处添加元素：
dq.append(i)

滑动窗口最大值问题Python完整代码：

from collections import deque

class Solution():
    def maxSlidingWindow(self, nums, k):

        dq = deque(maxlen=k)
        res = []

        for i in range(len(nums)):
            # 保持队首元素最大
            while (len(dq) != 0) and (nums[dq[-1]] < nums[i]):
                dq.pop()

            dq.append(i)

            if i >= (k - 1):
                res.append(nums[dq[0]])

        return res


if __name__ == '__main__':
    solu = Solution()
    print(solu.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))

输出结果：

我理解的双端队列解决滑动窗口最大值问题的核心思想：保持队首元素在原数组中的值最大，这样就能保证双端队列队首元素始终是当前滑动窗口内最大的