牛客3750题滑动窗口最大值解析：双端队列优化解法与代码详解

一、题目解读

牛客3750题要求在一个给定的整数数组中，计算固定大小为k的滑动窗口内元素的最大值。例如，当窗口滑动时，需要实时输出每个窗口中的最大值序列。该问题考察对滑动窗口算法的理解，以及如何高效维护窗口内的元素关系。

二、解题思路

采用双端队列（deque）维护单调递减队列的巧妙解法。核心思想是：队列中仅存储数组下标，保证队头为当前窗口的最大值下标，并通过以下规则动态维护：

    1. 当新元素进入窗口时，从队尾弹出所有小于新元素的元素，确保队列单调递减；

    2. 当窗口左边界移动时，从队头弹出超出窗口范围的元素。

通过该策略，队头始终指向窗口内最大值，避免了对窗口内元素的重复遍历。

三、解题步骤

1. 初始化结果数组与双端队列；

2. 遍历数组，若队列不空且队头下标已超出窗口范围，弹出队头；

3. 从队尾弹出所有小于当前元素的下标，保持队列单调递减；

4. 将当前下标入队；

5. 当窗口形成（即遍历至窗口大小-1时），记录队头元素值至结果数组；

6. 遍历结束后返回结果。

四、代码和注释

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, int size) {
        vector<int> result; // 存储结果
        // 处理特殊情况：窗口大小为0或大于数组长度
        if (size == 0 || size > num.size()) return result;

        deque<int> dq; // 存储下标，维护单调递减队列

        for (int i = 0; i < num.size(); ++i) {
            // 移除超出窗口范围的元素
            while (!dq.empty() && dq.front() <= (int)(i - size)) {
                dq.pop_front();
            }

            // 维护单调递减性质
            while (!dq.empty() && num[dq.back()] <= num[i]) {
                dq.pop_back();
            }

            dq.push_back(i); // 当前下标入队

            // 当窗口形成后开始记录结果
            if (i >= (int)(size - 1)) {
                result.push_back(num[dq.front()]); // 队头为最大值下标
            }
        }
        return result;
    }
};

五、总结

本解法通过双端队列优化，将时间复杂度降至O(n)，空间复杂度为O(k)。关键在于利用队列单调性避免重复比较，实现窗口滑动时的高效最大值获取。理解“单调队列维护”与“窗口边界处理”的逻辑是解决此类问题的核心。

滑动窗口