day13 代码随想录算法训练营 239. 滑动窗口最大值-526互联

题目：239. 滑动窗口最大值

我的感悟：

来难度了，有点意思，

理解难点：

需要实现自定义队列，
看了国外的解题思路和其他的回答，感觉还是卡尔的思路，更有意思。
实现队列：
- pop只弹出左边边界且左边界为最大值的时候
- push 要维护队列里的大到小的单调性。把队尾小的都卷走
- front查询最大值

代码难点：

代码示例：

from collections import deque
from typing import List


class MyQueue:  # 单调队列（从大到小
    def __init__(self):
        self.queue = deque()  # 这里需要使用deque实现单调队列，直接使用list会超时

    # 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    # 同时pop之前判断队列当前是否为空。
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()  # list.pop()时间复杂度为O(n),这里需要使用collections.deque()

    # 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    # 这样就保持了队列里的数值是单调从大到小的了。
    def push(self, value):
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)

    # 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    def front(self):

        return self.queue[0]


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        result = []
        for i in range(k):  # 先将前k的元素放进队列
            que.push(nums[i])
        result.append(que.front())  # result 记录前k的元素的最大值
        print("窗口之前现在值:", que.queue)
        for i in range(k, len(nums)):
            que.pop(nums[i - k])  # 滑动窗口移除最前面元素
            que.push(nums[i])  # 滑动窗口前加入最后面的元素
            print("nums[i]=", nums[i], "现在队列里:", que.queue)
            result.append(que.front())  # 记录对应的最大值
        return result


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