华为OD技术面试手撕真题：滑动窗口最大值

问题描述

给定一个数组 nums 和一个整数 k，请你找到所有滑动窗口里的最大值。返回的结果是一个数组，其中每个元素是对应窗口的最大值。

例如，对于输入数组 nums = [1, 3, -1, -3, 5, 3, 6, 7] 和 k = 3，滑动窗口的最大值是 [3, 3, 5, 5, 6, 7]。

思路分析

我们可以使用双端队列（Deque）来高效地解决这个问题。滑动窗口的大小为 k，我们需要保持窗口内的最大值，并随着窗口的移动更新最大值。基本的做法如下：

1. 使用双端队列：我们会使用一个Deque存储数组元素的索引，而不是其值。这个Deque的特点是，顶部总是当前窗口的最大值的索引。

2. 维护Deque的性质：

3. 每当新元素到达时，我们需要从Deque的尾部移除所有小于当前元素的索引，因为它们不可能是窗口的最大值。

4. 同时，我们还需要确保Deque中存储的索引是有效的，即索引不超过当前窗口的范围。

5. 更新结果：当我们的窗口形成（即i >= k - 1时），我们将Deque的头部元素对应的值加入结果数组中。

代码实现

以下是该问题的C++和Python代码实现。

C++ 实现

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    if (nums.empty() || k <= 0) return result;

    deque<int> deq;

    for (int i = 0; i < nums.size(); i++) {
        // 移除不在窗口范围内的元素
        if (!deq.empty() && deq.front() == i - k) {
            deq.pop_front();
        }

        // 移除所有小于当前元素的索引
        while (!deq.empty() && nums[deq.back()] < nums[i]) {
            deq.pop_back();
        }

        deq.push_back(i); // 添加当前元素索引

        // 窗口形成后添加结果
        if (i >= k - 1) {
            result.push_back(nums[deq.front()]);
        }
    }

    return result;
}

Python 实现

from collections import deque

def maxSlidingWindow(nums, k):
    result = []
    if not nums or k == 0:
        return result

    deq = deque()

    for i in range(len(nums)):
        # 移除不在窗口范围内的元素
        if deq and deq[0] == i - k:
            deq.popleft()

        # 移除所有小于当前元素的索引
        while deq and nums[deq[-1]] < nums[i]:
            deq.pop()

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

        # 窗口形成后添加结果
        if i >= k - 1:
            result.append(nums[deq[0]])

    return result

复杂度分析

1. 时间复杂度：O(n)，每个元素入队和出队均至多各一次，因此整体时间复杂度为O(n)。

2. 空间复杂度：O(k)，用于存储双端队列的空间复杂度。

通过上述方式，我们能够高效处理滑动窗口最大值的问题，保证在面试中能快速且准确地解决此类问题。希望这篇文章对你在面试中有所帮助！