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

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

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

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

#### 一、问题描述

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

#### 二、暴力解法

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

```python
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) 时间内更新窗口的最大值，并处理窗口的滑动。

**算法思路**：

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

```python
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 个元素的索引。

#### 五、变种与扩展

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

#### 六、总结

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

该分类下的相关小册推荐：

数据结构与算法(上)

数据结构与算法(下)

数据结构与算法(中)

编程之道-算法面试(上)

编程之道-算法面试(下)

业务开发实用算法精讲

数据结构与算法之美