题解 | 滑动窗口的最大值

1、解题思路

1. 暴力法：对于每个窗口，遍历窗口内的所有元素找出最大值。时间复杂度为 O(n*k)，其中 n 是数组长度，k 是窗口大小。这会超出时间限制。
2. 双端队列优化 ：使用一个双端队列（deque）来存储当前窗口中的可能成为最大值的元素索引。维护队列的单调性：队列中的元素索引对应数组中的值从大到小排列。遍历数组时：移除队列中不在当前窗口范围内的索引。移除队列中比当前元素小的索引（因为它们不可能成为后续窗口的最大值）。将当前元素索引加入队列。记录当前窗口的最大值（队列首元素对应的值）。

2、代码实现

C++

#include <deque>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @param size int整型
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> res;
        if (num.empty() || size == 0 || size > num.size()) {
            return res;
        }

        deque<int> dq;
        for (int i = 0; i < num.size(); ++i) {
            // 移除队列中不在当前窗口范围内得索引
            while (!dq.empty() && dq.front() <= i - size) {
                dq.pop_front();
            }

            // 移除队列中比当前元素小的索引
            while (!dq.empty() && num[dq.back()] < num[i]) {
                dq.pop_back();
            }

            // 将当前元素索引加入队列
            dq.push_back(i);
            // 记录当前窗口的最大值
            if (i >= size - 1) {
                res.push_back(num[dq.front()]);
            }
        }

        return res;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        if (num == null || size == 0 || size > num.length) {
            return res;
        }

        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < num.length; ++i) {
            // 移除队列中不在当前窗口范围内的索引
            while (!deque.isEmpty() && deque.peekFirst() <= i - size) {
                deque.pollFirst();
            }
            // 移除队列中比当前元素小的索引
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.pollLast();
            }
            // 将当前元素索引加入队列
            deque.offerLast(i);
            // 记录当前窗口的最大值
            if (i >= size - 1) {
                res.add(num[deque.peekFirst()]);
            }
        }
        return res;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
#
from collections import deque

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        res = []
        if not num or size == 0 or size > len(num):
            return res

        dq = deque()
        for i in range(len(num)):
            # 移除队列中不在当前窗口范围内的索引
            while dq and dq[0] <= i - size:
                dq.popleft()
            # 移除队列中比当前元素小的索引
            while dq and num[dq[-1]] < num[i]:
                dq.pop()
            # 将当前元素索引加入队列
            dq.append(i)
            # 记录当前窗口的最大值
            if i >= size - 1:
                res.append(num[dq[0]])
        return res

3、复杂度分析

• 空间复杂度 O(n)
• 时间复杂度 O(n)