64 滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里的数值的最大值。

示例：

输入: [2,3,4,2,6,2,5,1], 3
输出: [4,4,6,6,6,5]

解题思路

核心思想：使用双向队列维护窗口内的最大值。

时间复杂度：O(n) 空间复杂度：O(k)

Python 实现

from collections import deque

def max_in_windows(nums, size):
    """
    滑动窗口的最大值

    Args:
        nums: 数组
        size: 窗口大小

    Returns:
        list: 每个窗口的最大值
    """
    if not nums or size <= 0 or size > len(nums):
        return []

    result = []
    dq = deque()  # 存储索引，队首是当前窗口最大值的索引

    for i in range(len(nums)):
        # 移除超出窗口的元素
        if dq and dq[0] <= i - size:
            dq.popleft()

        # 移除比当前元素小的元素
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        # 添加当前元素的索引
        dq.append(i)

        # 窗口形成后，记录最大值
        if i >= size - 1:
            result.append(nums[dq[0]])

    return result


# 测试代码
if __name__ == "__main__":
    test_cases = [
        ([2, 3, 4, 2, 6, 2, 5, 1], 3),
        ([1, 2, 3, 4, 5], 2),
    ]

    for nums, size in test_cases:
        result = max_in_windows(nums, size)
        print(f"数组: {nums}, 窗口大小: {size}")
        print(f"最大值: {result}")

# 输出:
# 数组: [2, 3, 4, 2, 6, 2, 5, 1], 窗口大小: 3
# 最大值: [4, 4, 6, 6, 6, 5]
# 数组: [1, 2, 3, 4, 5], 窗口大小: 2
# 最大值: [2, 3, 4, 5]