Sliding Window
Time Limit: 12000MS | Memory Limit: 65536K | |
Total Submissions: 35975 | Accepted: 10649 | |
Case Time Limit: 5000MS |
Description
An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
[1 3 -1] -3 5 3 6 7 | -1 | 3 |
1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
1 3 -1 -3 5 [3 6 7] | 3 | 7 |
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
Sample Input
8 3 1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7
题意同上题。
思路:
单调队列。一个单调队列保存非递增序列,一个单调队列维护非递减序列。当滑动一个窗口时就将新元素与最后一个元素比较,后插入队尾。输出的时候输出队头元素,要判断队头元素下标是否符合当前的 l,r 值范围内。
AC:
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAX = 1000005; int n, k; int num[MAX]; int q_max[MAX], q_min[MAX]; void Max () { int s = 0, e = -1; int l = 1, r = 1 + k - 1; q_max[++e] = 1; for (int i = l; i <= r; ++i) { if(num[i] <= num[q_max[e]]) q_max[++e] = i; else { while(num[i] > num[q_max[e]] && e != s - 1) --e; q_max[++e] = i; } } printf("%d", num[q_max[s]]); for (++l, ++r; r <= n; ++l, ++r) { if (num[r] <= num[q_max[e]]) q_max[++e] = r; else { while(num[r] > num[q_max[e]] && e != s - 1) --e; q_max[++e] = r; } while (q_max[s] > r || q_max[s] < l) ++s; printf(" %d",num[q_max[s]]); } printf("\n"); } void Min () { int s = 0, e = -1; int l = 1, r = 1 + k - 1; q_min[++e] = 1; for (int i = l; i <= r; ++i) { if(num[i] >= num[q_min[e]]) q_min[++e] = i; else { while(num[i] < num[q_min[e]] && e != s - 1) --e; q_min[++e] = i; } } printf("%d", num[q_min[s]]); for (++l, ++r; r <= n; ++l, ++r) { if (num[r] >= num[q_min[e]]) q_min[++e] = r; else { while(num[r] < num[q_min[e]] && e != s - 1) --e; q_min[++e] = r; } while (q_min[s] > r || q_min[s] < l) ++s; printf(" %d",num[q_min[s]]); } printf("\n"); } int main () { while (~scanf("%d%d", &n, &k)) { for (int i = 1; i <= n; ++i) scanf("%d", &num[i]); Min(); Max(); } return 0; }
相关推荐
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
我的博客链接:http://blog.csdn.net/CABI_ZGX
这是来自poj的一道关于单调队列的题目。分为max_qu和min_qu两部分来做。
滑动窗口软件代码,UDP Sliding Window Protocol
Sliding Window_(System Approach 4ed)
Sliding window ,滑窗协议 ,实验报告,代码,实验截图等,仅供参考学习
Qt5.5.1+msvc2013使用QSplitter控件实现滑动窗口,根据程序需求可设置为固定和可移动
基于滑动窗口的三维手指检测和跟踪算法,吴俊,乔文静,本文提出了一种面向RGB-D深度图像序列的基于滑动窗口的三维手指检测跟踪算法 (3dFDT) 。微软的Kinect被作为获取三维深度图像序列的摄像�
sliding_window算法的python版本,分享给有需要的人
Sliding Window Protocol Implementatoin
TCP Sliding Window滑动窗口协议演示动画,Flash播放,可以调整参数
2. Pattern Sliding Window.zip
一篇流数据分析方面的经典SCI论文,2013年发表的
滑动窗口协议解析
var slidingWindow = SlidingWindow ( alloc , free , options ) ; alloc是一个分配东西的函数。 它接收两个参数:第一个参数是要分配的块的index 。 第二个参数是一个可选参数,可以在move()第二个参数处传输。 ...
本文详细分析了基于滑动窗口的视觉slam或者视觉里程计方案的一致性问题
Sliding-window-topk.ppt
Sliding Window:实现使用GBN协议和UDP进行通信的发送方和接收方 一点警告:这里发生了很多内存泄漏,因此克隆它修复并从中获得乐趣。 我有点想念的另一件事是解释滑动部分,它确实是分块完成的。
sliding window and active constellation extension for fbmc oqam signal
MATLAB典型代码 (示例面部检测结果来自anXDdd。) 项目4:带有滑动窗口的人脸检测 简短的 截止时间: 1月1日,晚上11:59。 所需文件:results / index.md和代码/ ...滑动窗口模型在概念上很简单:将所有图像块独立地...