(笔试题)滑动窗口的最大值
题目:
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。
例如,如果输入数组{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]}。
思路:
假设窗口大小为w,
1、简单的方法:
遍历数组,从数组第w-1位开始,每次移动一位,并计算窗口w的最大值。
时间复杂度:
计算窗口的最大值需O(w),移动n-w+1次,时间复杂度为O(nw)
2、最大堆方法:
构建一个窗口w大小的最大堆,每次从堆中取出窗口的最大值,随着窗口往右滑动,需要将堆中不属于窗口的堆顶元素删除。
时间复杂度:
正常情况下,往堆中插入数据为O(lgw),如果数组有序,则为O(lgn),因为滑动过程中没有元素从堆中被删除,滑动n-w+1次,复杂度为O(nlgn).
3、双队列方法:
最大堆解法在堆中保存有冗余的元素,比如原来堆中元素为[10 5 3],新的元素为11,则此时堆中会保存有[11 5 3]。其实此时可以清空整个队列,然后再将11加入到队列即可,即只在队列中保持[11]。使用双向队列可以满足要求,滑动窗口的最大值总是保存在队列首部,队列里面的数据总是从大到小排列。当遇到比当前滑动窗口最大值更大的值时,则将队列清空,并将新的最大值插入到队列中。如果遇到的值比当前最大值小,则直接插入到队列尾部。每次移动的时候需要判断当前的最大值是否在有效范围,如果不在,则需要将其从队列中删除。由于每个元素最多进队和出队各一次,因此该算法时间复杂度为O(N)。
代码:
1、简单方法:
int getMax(const int A[],int size){ int mx=A[0]; for(int i=1;i<size;i++){ if(A[i]>mx) mx=A[i]; } return mx; } vector<int> maxInWindows(const int A[],int n,int size){ vector<int> result; for(int i=0;i<n-size;i++){ int num=getMax(A+i,size); result.push_back(num); } return result; }
2、最大堆、双队列方法
class Solution { public: //最大堆实现,复杂度O(nlogn) typedef pair<int,int> Pair; vector<int> maxInWindows(const vector<int> &num, unsigned int size) { vector<int> result; priority_queue<Pair> Q; if (num.size() < size || size < 1) return result; for (int i = 0; i < size-1; i++) Q.push(Pair(num[i],i)); for (int i = size-1; i < num.size(); i++) { Q.push(Pair(num[i],i)); Pair p = Q.top(); while(p.second < i-(size-1)) { Q.pop(); p = Q.top(); } result.push_back(p.first); } return result; } // 双向队列实现,复杂度O(n) vector<int> maxInWindows(const vector<int> &num, unsigned int size) { vector<int> result; deque<int> Q; // int n = num.size(); if(num.size()<size || size<=0) return result; for (int i = 0; i < size; i++) { while (!Q.empty() && num[i] > num[Q.back()]) Q.pop_back(); Q.push_back(i); } for (int i = size; i < num.size(); i++) { result.push_back(num[Q.front()]); while (!Q.empty() && num[i] >= num[Q.back()]) Q.pop_back(); while (!Q.empty() && Q.front() <= i - size) Q.pop_front(); Q.push_back(i); } result.push_back(num[Q.front()]); return result; } };
相关文章
- Silverlight 5 RC新特性探索系列:12.Silverlight 5 RC 窗口模式下访问自定义DLL和WIN32 API
- VS里属性窗口中的生成操作释义
- Qt-Qt的窗口显示的内容转化为图片
- Java实现 LeetCode 757 设置交集大小至少为2(排序+滑动窗口)
- Java实现 LeetCode 567 字符串的排列(滑动窗口,处理区间内的字符数量)
- Java实现 LeetCode 480 滑动窗口中位数
- Java实现 LeetCode 239 滑动窗口最大值
- [工具] Textify – 复制不可能的窗口内容[Win]
- WINDOWS窗口创建及消息处理代码
- Flink窗口Window机制详解
- 154. 滑动窗口
- 2024. 考试的最大困扰度(滑动窗口)
- LeetCode-1234. 替换子串得到平衡字符串【滑动窗口,字符串】
- LeetCode-713. 乘积小于 K 的子数组【滑动窗口】
- 滑动窗口协议
- 在弹出对话框窗口里显示 SAP ABAP ALV 列表
- Qt中窗口关闭自动销毁的实现示例
- Qt setAttribute设置窗口属性
- Qt 主窗口与子窗口之间传值
- Gtk常用控件 按钮 图片控件 进度条 滑动窗口 分栏列表
- 剑指 Offer II 041. 滑动窗口的平均值
- Qt程序启动时会出现一闪而过的小窗口怎么办
- 滑动窗口
- Win10系统开机自动弹出cmd窗口解决方法
- 任务栏发明之前,窗口是如何最小化的?
- 应该在什么时候使用Sunken窗口风格
- VC++ Win32界面编程中的窗口风格要点总结(附源码)
- Python 小白从零开始 PyQt5 项目实战(6)窗口切换的堆叠布局
- 刷题记录:牛客NC50528滑动窗口
- 剑指 Offer 59 - I. 滑动窗口的最大值
- 滑动窗口(C++,Java)
- win7系统怎么进行窗口大小的固定