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

贾蔷
• 阅读 58

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

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

点赞
收藏
评论区
推荐文章
常用限流算法详解
一、有哪些常用的限流算法1.固定窗口限流;2.滑动窗口限流;3.漏桶算法限流;4.令牌桶算法限流。二、4种限流算法介绍1.固定窗口限流举例说明:假设时间窗口大小为5s,则0到5s为第一个窗口,5到10s为第二个窗
贾蔷 贾蔷
1个月前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
贾蔷 贾蔷
1个月前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
贾蔷 贾蔷
1个月前
洛谷P1168题终极解析:双堆法高效计算动态中位数 | 数据结构实战教程
一、问题理解与算法思路题目要求我们动态维护一个序列,并在每次读取奇数个数字时输出当前序列的中位数。这道题考察了两个核心算法点:堆数据结构的应用和中位数的高效计算。我们采用双堆法(一个大根堆和一个小根堆)来高效解决这个问题。‌解题关键步骤‌:使用大根堆存储较
深度学习 深度学习
1个月前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
2星期前
动态规划预处理+滑动窗口:力扣2420题"好下标"解法详解
一、问题理解题目要求找出中满足特定条件的"好下标":对于下标i,其左侧k个元素必须是非递增的,右侧k个元素必须是非递减的。这是典型的数组区间性质检查问题。二、解题思路1.预处理核心思想是通过两次预处理:left数组:记录每个位置向左的非长度right数组:
深度学习 深度学习
2星期前
NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解
一、题目解读问题(,)要求使用给定数量的火柴棒,构造形如ABC的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式数量。题目核心在于将数字拆解与火柴棒消耗建模为数学问题,寻找高效解法。二、解题思路采用火柴棒计数策略:1.关系
贾蔷 贾蔷
1星期前
牛客13278题详解:句子单词反转(C++实现)
一、题目解读13278题要求编写函数实现句子中单词顺序的反转,例如将"HelloWorld"转换为"WorldHello"。需注意处理首尾空格、单词间空格数量保持原样,仅单词顺序颠倒。题目考察对操作的掌握,特别是分割与重组技巧。二、解题思路采用:1.预处理
贾蔷 贾蔷
6天前
洛谷P1102题解:利用哈希表优化的数对统计 C++代码解析
一、题目解读P1102题要求处理一组整数与常数C,统计数组中是否存在元素A与B满足ABC。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素,时间复杂度需优化以避免暴力遍历。二、解题思路采用(unorderedmap)实现高效统计。首先遍
深度学习 深度学习
6天前
LeetCode 2576题解:双指针法求解最多标记下标(排序+贪心策略)
一、题目解读2576题要求在一个整数中寻找最多可标记的下标对:若nums法”的组合思路:1.排序预处理:对原数组nums进行升序排序,确保相同元素聚集,便于后续配对。2.双划分:将排序后的数组分为左右两半(左指针left0,右指针rightn/2),从