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

贾蔷
• 阅读 4

牛客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题滑动窗口最大值解析:双端队列优化解法与代码详解

点赞
收藏
评论区
推荐文章
DaLongggggg DaLongggggg
4年前
python刷题-数列特征
问题描述给出n个数,找出这n个数的最大值,最小值,和。输入格式第一行为整数n,表示数的个数。第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。输出格式输出三行,每行一个整数。第一行表示这些数中的最大值,第二行表示这些数中的最小值,第三行表示这些数的和。样例输入513245样例输出5211数据规模与约定1<n<10000。
常用限流算法详解
一、有哪些常用的限流算法1.固定窗口限流;2.滑动窗口限流;3.漏桶算法限流;4.令牌桶算法限流。二、4种限流算法介绍1.固定窗口限流举例说明:假设时间窗口大小为5s,则0到5s为第一个窗口,5到10s为第二个窗
贾蔷 贾蔷
1个月前
力扣933题:队列的妙用:如何高效统计最近请求
题目重解:我们需要设计一个能统计最近3000毫秒内请求次数的系统。每当新的请求到来时,它会带有时间戳t,我们需要返回过去3000毫秒内(包括当前)发生的请求总数。这就像是在时间轴上维护一个滑动窗口,只关注最近3秒内的活动。解题思路解析:1.初始化:创建空队
贾蔷 贾蔷
1个月前
NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析
一、题目描述简要描述题目:例如,在一个n×n的方格图中,每个格子包含一个正整数。需要选择两条从左上角到右下角的路径,路径可重复经过格子,但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。二、解题思路与算法分析1.问题分析1.问题核心是求解两条不交
贾蔷 贾蔷
1星期前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
贾蔷 贾蔷
1星期前
CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解
一、题目解读CSPJ2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记录,优化总费用。该问题考察对时间窗口与动态资源管理的理解,需
贾蔷 贾蔷
1星期前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
贾蔷 贾蔷
1星期前
洛谷P1168题终极解析:双堆法高效计算动态中位数 | 数据结构实战教程
一、问题理解与算法思路题目要求我们动态维护一个序列,并在每次读取奇数个数字时输出当前序列的中位数。这道题考察了两个核心算法点:堆数据结构的应用和中位数的高效计算。我们采用双堆法(一个大根堆和一个小根堆)来高效解决这个问题。‌解题关键步骤‌:使用大根堆存储较
深度学习 深度学习
1星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
9小时前
动态规划预处理+滑动窗口:力扣2420题"好下标"解法详解
一、问题理解题目要求找出中满足特定条件的"好下标":对于下标i,其左侧k个元素必须是非递增的,右侧k个元素必须是非递减的。这是典型的数组区间性质检查问题。二、解题思路1.预处理核心思想是通过两次预处理:left数组:记录每个位置向左的非长度right数组: