跟着姚桑学算法-滑动窗口的最大值

简介: 剑指offer算法

题. 滑动窗口的最大值

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。

例如,如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3,那么一共存在 6 个滑动窗口,它们的最大值分别为 [4,4,6,6,6,5]。

注意:

数据保证 k 大于 0,且 k 小于等于数组长度。

数据范围
数组长度 [1,1000]。

样例

输入:[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

【题解】--- 模拟滑动窗口

首先,最直接的做法当然是 模拟滑动窗口 的过程,每向右滑动一次都遍历一遍窗口内的数字找最大的输出,这样的复杂度是O(kn),我们可以考虑优化一下。

窗口向右滑动的过程实际上就是将处于窗口的第一个数字删除,同时在窗口的末尾添加一个新的数字,这就可以用双向队列来模拟,每次把尾部的数字弹出,再把新的数字压入到头部,然后找队列中最大的元素即可。

为了更快地找到最大的元素,我们可以在队列中只保留那些可能成为窗口最大元素的数字,去掉那些不可能成为窗口中最大元素的数字。

考虑这样一个情况,如果队列中进来一个较大的数字,那么队列中比这个数更小的数字就不可能再成为窗口中最大的元素了,因为这个大的数字是后进来的,一定会比之前早进入窗口的小的数字要晚离开窗口,那么那些早进入且比较小的数字就“永无出头之日”,所以就可以弹出队列。

于是我们维护一个双向单调队列,队列放的是元素的下标。我们假设该双端队列的队头是整个队列的最大元素所在下标,至队尾下标代表的元素值依次降低。初始时单调队列为空。

随着对数组的遍历过程中,每次插入元素前,首先需要看队头是否还能留在队列中,如果队头下标距离i超过了k,则应该出队。同时需要维护队列的单调性,如果nums[i]大于或等于队尾元素下标所对应的值,则当前队尾再也不可能充当某个滑动窗口的最大值了,故需要队尾出队。始终保持队中元素从队头到队尾单调递减。依次遍历一遍数组,每次队头就是每个滑动窗口的最大值所在下标。

复杂度分析:

每个元素最多入队出队一次,复杂度为O(n)

C++代码实现:

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int>res;
        deque<int>q;
        for(int i = 0; i < nums.size(); i++){
            if(!q.empty() && i-q.front() >= k)//判断队头是否需要出队
                q.pop_front();
            while(!q.empty()&&nums[q.back()]<nums[i])//维护队列单调性
                q.pop_back();
            q.push_back(i);
            if(i >= k-1){
                res.push_back(nums[q.front()]);//取队头作为窗口最大元素
            }
        }
        return res;
    }
};
目录
相关文章
|
算法
【算法】滑动窗口——最大连续1的个数
【算法】滑动窗口——最大连续1的个数
141 0
|
6月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
137 2
|
4月前
|
存储 机器学习/深度学习 监控
公司电脑上网监控中滑动窗口算法的理论构建与工程实现
本文提出一种基于滑动窗口算法的实时网络流量监控框架,旨在强化企业信息安全防护体系。系统采用分层架构设计,包含数据采集、处理与分析决策三大模块,通过 Java 实现核心功能。利用滑动窗口技术动态分析流量模式,结合阈值检测与机器学习模型识别异常行为。实验表明,该方案在保证高检测准确率的同时支持大规模并发处理,为企业数字化转型提供可靠保障。
92 0
|
6月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
131 3
|
7月前
|
存储 监控 算法
基于 PHP 语言的滑动窗口频率统计算法在公司局域网监控电脑日志分析中的应用研究
在当代企业网络架构中,公司局域网监控电脑系统需实时处理海量终端设备产生的连接日志。每台设备平均每分钟生成 3 至 5 条网络请求记录,这对监控系统的数据处理能力提出了极高要求。传统关系型数据库在应对这种高频写入场景时,性能往往难以令人满意。故而,引入特定的内存数据结构与优化算法成为必然选择。
148 3
|
算法
【算法】滑动窗口——最小覆盖子串
【算法】滑动窗口——最小覆盖子串
113 0
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
168 0
|
算法
【算法】滑动窗口——将x减到0的最小操作数
【算法】滑动窗口——将x减到0的最小操作数
125 0
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
算法
【算法】滑动窗口——长度最小的子数组
【算法】滑动窗口——长度最小的子数组
141 0

热门文章

最新文章