python算法例18 滑动窗口的最大值

2023-12-13 17:04:18

1. 问题描述

给定一个可能包含重复整数的数组和一个大小为k的滑动窗口,从左到右在数组中滑动这个窗口,找到数组中每个窗口内的最大值。

2. 问题示例

给出数组[1,2,7,7,8],滑动窗口大小为k=3,返回[7,7,8]。

3. 代码实现

使用双端队列(deque)来实现这个滑动窗口最大值的问题。具体的算法如下:

  1. 首先,创建一个双端队列 deque 和结果列表 result。
  2. 遍历数组,对于每个元素,执行以下操作:
    • 在队尾添加当前元素索引 i,但在添加之前,需要先将队尾小于当前元素的元素全部弹出,以确保队列中的元素是递减的。
    • 检查队首的元素是否已经超出窗口范围,如果是,则将其弹出。
    • 当达到窗口大小时,将队首元素加入结果列表中,即为当前窗口的最大值。
  3. 返回结果列表。
from collections import deque

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    
    result = []
    window = deque()
    
    for i in range(len(nums)):
        # 弹出队尾所有小于当前元素的值
        while window and nums[i] >= nums[window[-1]]:
            window.pop()
        
        # 将当前元素索引加入队尾
        window.append(i)
        
        # 检查队首元素是否超出窗口范围
        if window[0] <= i - k:
            window.popleft()
        
        # 达到窗口大小时,将队首元素加入结果列表
        if i >= k - 1:
            result.append(nums[window[0]])
    
    return result

# 测试示例
nums = [1, 2, 7, 7, 8]
k = 3
print(maxSlidingWindow(nums, k))  # 输出 [7, 7, 8]

使用了双端队列 deque 来维护当前窗口内的最大值索引,算法的时间复杂度是 O(n)。

文章来源:https://blog.csdn.net/m0_62110645/article/details/134972905
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。