博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
面试题65 滑动窗口的最大值
阅读量:5275 次
发布时间:2019-06-14

本文共 1093 字,大约阅读时间需要 3 分钟。

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
1 class Solution { 2 public: 3  vector
maxInWindows(const vector
&num, unsigned int size) { 4 vector
result; 5 deque
Q; 6 // int n = num.size(); 7 if(num.size()
num[Q.back()]) Q.pop_back();11 Q.push_back(i);12 }13 for (int i = size; i < num.size(); i++) {14 result.push_back(num[Q.front()]);15 while (!Q.empty() && num[i] >= num[Q.back()]) Q.pop_back();16 while (!Q.empty() && Q.front() <= i - size) Q.pop_front();17 Q.push_back(i);18 }19 result.push_back(num[Q.front()]);20 return result;21 }22 23 };

 

转载于:https://www.cnblogs.com/wanderingzj/p/5375759.html

你可能感兴趣的文章
百度地图api服务端根据经纬度得到地址
查看>>
使用yum更新时不升级Linux内核的方法
查看>>
sqlserver计算时间差DATEDIFF 函数
查看>>
51nod1307(暴力树剖/二分&dfs/并查集)
查看>>
用户体验分析: 以 “南通市图书馆微信公众号” 为例
查看>>
linux的管道 |和grep命令以及一些其他命令(diff,echo,cat,date,time,wc,which,whereis,gzip,zcat,unzip,sort)...
查看>>
Nginx和PHP-FPM的启动、重启、停止脚本分享
查看>>
cookie 和session 的区别详解
查看>>
Vuex-状态管理模式
查看>>
浮点数运算的精度问题:以js语言为例
查看>>
数据挖掘领域十大经典算法
查看>>
【C语言】09-字符串
查看>>
数据库连接及线程池
查看>>
解决android应用程序适用新老android系统版本方法
查看>>
Oracle SQL语句执行过程
查看>>
Oracle 中的SID是什么意思?有什么作用?
查看>>
关于http协议
查看>>
jquery validation remote进行唯一性验证时只使用自定义参数,不使用默认参数
查看>>
软件工程个人项目——买书的最低价格
查看>>
5-21
查看>>