12 | 面试题：返回滑动窗口中的最大值-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

12 | 面试题：返回滑动窗口中的最大值

在算法面试中，滑动窗口问题是一类常见且富有挑战性的题目，它要求算法在处理数据流或数组时，能够高效地维护一个固定大小的窗口，并在这个窗口上执行特定的计算任务。其中，“返回滑动窗口中的最大值”是一个经典问题，它不仅考察了应聘者对数据结构（如双端队列、优先队列等）的理解，还检验了其对时间复杂度优化的能力。本章节将详细探讨这一问题的多种解法，包括暴力解法、使用双端队列（Deque）的优化解法，以及在此基础上的一些变种和扩展。

一、问题描述

给定一个整数数组 nums 和一个整数 k，要求编写一个函数，该函数能够接收一个整数 i（代表当前窗口的起始位置），并返回以 i 为起始位置、长度为 k 的滑动窗口中的最大值。注意，这里讨论的是一个更通用的版本，即对于每个可能的起始位置 i（0 <= i <= nums.length - k），都需要返回对应的窗口最大值。为了简化问题，我们通常先解决连续滑动窗口的最大值问题，即固定 i 的变化，逐步向右滑动窗口。

二、暴力解法

最直接的想法是，对于每个可能的窗口起始位置 i，遍历窗口内的所有元素，找到最大值。这种方法的时间复杂度为 O(n*k)，其中 n 是数组 nums 的长度。对于大数据集，这种解法显然不够高效。

def maxSlidingWindow_bruteForce(nums, k):
    result = []
    for i in range(len(nums) - k + 1):
        max_val = float('-inf')
        for j in range(i, i + k):
            max_val = max(max_val, nums[j])
        result.append(max_val)
    return result

三、使用双端队列（Deque）的优化解法

为了降低时间复杂度，我们可以利用双端队列（Deque）来维护一个递减的窗口最大值序列。队列中存储的是数组元素的索引，而不是值本身，这样做的好处是可以在 O(1) 时间内更新窗口的最大值，并处理窗口的滑动。

算法思路：

初始化一个双端队列 deque，用于存储窗口内可能的最大值元素的索引。
遍历数组 nums，对于每个元素 nums[i]：
- 移除队列左侧（队首）所有小于等于 i-k 的索引，因为这些索引对应的元素已经不在当前窗口内。
- 从队列右侧（队尾）移除所有小于 nums[i] 的元素的索引，因为这些元素即使在当前窗口内，也不可能是最大值。
- 将当前元素的索引 i 加入队列右侧。
- 如果队列非空，则队列左侧（队首）的索引对应的元素就是当前窗口的最大值。
遍历过程中，将每个窗口的最大值加入结果列表 result。

from collections import deque
def maxSlidingWindow(nums, k):
    deque = []
    result = []
    for i in range(len(nums)):
        # Step 1: Remove indices of elements outside the window
        if deque and deque[0] <= i - k:
            deque.popleft()
        # Step 2: Remove indices of smaller elements from the right
        while deque and nums[deque[-1]] < nums[i]:
            deque.pop()
        # Step 3: Add current index to the deque
        deque.append(i)
        # Step 4: Record the maximum when the window is fully formed
        if i >= k - 1:
            result.append(nums[deque[0]])
    return result

四、算法分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。每个元素最多被加入和移出队列各一次。
空间复杂度：O(k)，队列中最多存储 k 个元素的索引。

五、变种与扩展

最小值滑动窗口：与最大值滑动窗口类似，只是将比较和存储的逻辑改为针对最小值。
滑动窗口内的和/平均值：修改算法以计算滑动窗口内元素的和或平均值。
动态变化的窗口大小：在某些问题中，窗口的大小 k 可能不是固定的，而是根据某些条件动态变化。这要求算法能够灵活地调整窗口大小。
多维数组滑动窗口：在二维或更高维度的数组上执行滑动窗口操作，可能需要额外的数据结构或算法设计来优化性能。

六、总结

“返回滑动窗口中的最大值”是一个经典的算法面试题，通过这个问题，可以深入考察应聘者对数据结构、算法设计和时间空间复杂度优化的理解。利用双端队列（Deque）可以有效地解决这一问题，将时间复杂度降低到 O(n)。此外，通过探讨问题的变种和扩展，可以进一步提升算法思维能力和问题解决能力。