当前位置:首页 > 牛客 > 牛客3750题滑动窗口最大值解析:双端队列优化解法与代码详解

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

3天前

牛客3750题滑动窗口最大值解析:双端队列优化解法与代码详解 滑动窗口最大值 双端队列 单调递减队列 时间复杂度O(n) 牛客3750题 第1张

一、题目解读

牛客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)。关键在于利用队列单调性避免重复比较,实现窗口滑动时的高效最大值获取。理解“单调队列维护”与“窗口边界处理”的逻辑是解决此类问题的核心。


滑动窗口

原创内容 转载请注明出处

分享给朋友:

相关文章

牛客4493题解析:桶排序优化求解最大间隔问题(附代码详解)

牛客4493题解析:桶排序优化求解最大间隔问题(附代码详解)

一、题目解读牛客4493题要求在一个整数数组中寻找最大间隔,即数组中任意两个元素之间的最大差值。题目强调需要高效算法,尤其在处理大规模数据时仍需保持性能。理解题目核心在于如何快速定位元素间的最远距离,...

牛客3750题解题报告:滑动窗口最大值的高效解法(C++代码详解)

牛客3750题解题报告:滑动窗口最大值的高效解法(C++代码详解)

一、题目解读牛客3750题要求在一个给定的整数数组中,计算指定窗口大小下的滑动窗口最大值。例如,输入数组num=[1,3,-1,-3,5,3,6,7],窗口大小为size=3时,需输出每个窗口内的最大...

力扣922题解法深度解析:双指针优化奇偶排序(含代码实现)

力扣922题解法深度解析:双指针优化奇偶排序(含代码实现)

一、题目解读力扣922题要求将给定数组按奇偶性重新排列,使得所有偶数位于奇数之前,同时保持原有相对顺序不变。例如,输入[4,5,2,7]应输出[4,2,5,7]。题目强调“原地”操作,即不得使用额外数...

2024年GESP四级宝箱题(洛谷P4006)题解:滑动窗口算法优化最长子序列和

2024年GESP四级宝箱题(洛谷P4006)题解:滑动窗口算法优化最长子序列和

一、题目解读本题为2024年GESP四级中的“宝箱”问题(对应洛谷P4006),要求在一个由n个宝箱组成的序列中,找出一个连续子序列,使得该子序列中宝箱价值之和最大,且子序列中最大值与最小值的差不超过...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。