当前位置：首页 > article >正文

力扣：239. 滑动窗口最大值

article 2024/9/24 6:21:36

题目：

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

返回滑动窗口中的最大值。

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

代码实现及思路：

from collections import deque

# 自定义队列
class MyQueue:
    def __init__(self):
        # 创建一个双端队列 作为基本数据结构
        self.queue = deque()

    def pop(self, value):
        # 当队列的头节点值和传入值相等 就把那个节点pop
        if self.queue and value == self.queue[0]:
            self.queue.popleft()

    def push(self, value):
        # 对尾部进行处理，保留递减数组
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        # 把每次滑动的新数加入尾部
        self.queue.append(value)

    def get_max(self):
        # 返回最大值即头部的节点
        return self.queue[0]


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        res = []
        # 先将前k的元素放入队列
        for i in range(k):
            que.push(nums[i])
        res.append(que.get_max())
        # 遍历后面元素
        for i in range(k, len(nums)):
            #窗口向右移动，弹出队列中不在窗口内的元素
            que.pop(nums[i - k])
            #向队列添加元素
            que.push(nums[i])
            # 记录当前窗口最大值
            res.append(que.get_max())
        return res