Sliding Window
Time Limit: 12000MS | Memory Limit: 65536K | |
Total Submissions: 35974 | Accepted: 10648 | |
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
题意:
给出 N(1 ~ 10 ^ 6) 和 K,后给出 N 个数,滑动窗口的宽度为 K,说明每次只能看到 K 个数,窗口从左滑到右,输出每次滑动的最小值和最大值。
思路:
RMQ。维护区间的最小值 和 最大值。求区间最值问题。O(n log n)的预处理 + O(1)的查询。但是用二维数组保存的话会 MLE,所以要优化一下空间,RMQ更新长度更新到 k 长度的 ans( 2 ^ ans <= k) 即可,不需要更新完全部的长度 n 长度的 ans 值(2 ^ ans <= n),这样的话,可以省略掉第二维来节省空间。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 1000005; int n, k, ans; int Min[MAX], Max[MAX]; void RMQ_init() { for (int j = 1; j <= ans; ++j) { for (int i = 0; i + (1 << j) - 1 < n; ++i) { Max[i] = max(Max[i], Max[i + (1 << (j - 1))]); Min[i] = min(Min[i], Min[i + (1 << (j - 1))]); } } } int main () { while (~scanf("%d%d", &n, &k)) { ans = 0; for (int i = 0; i < n; ++i) { scanf("%d", &Min[i]); Max[i] = Min[i]; } while ((1 << (ans + 1)) <= k) ++ans; RMQ_init(); for (int i = 0; i <= n - k; ++i) { printf("%d", min(Min[i], Min[i + k - (1 << ans)])); i == (n - k) ? printf("\n") : printf(" "); } for (int i = 0; i <= n - k; ++i) { printf("%d", max(Max[i], Max[i + k - (1 << ans)])); i == (n - k) ? printf("\n") : printf(" "); } } return 0; }
相关推荐
滑动窗口软件代码,UDP Sliding Window Protocol
Sliding Window_(System Approach 4ed)
Sliding window ,滑窗协议 ,实验报告,代码,实验截图等,仅供参考学习
Qt5.5.1+msvc2013使用QSplitter控件实现滑动窗口,根据程序需求可设置为固定和可移动
这是来自poj的一道关于单调队列的题目。分为max_qu和min_qu两部分来做。
基于滑动窗口的三维手指检测和跟踪算法,吴俊,乔文静,本文提出了一种面向RGB-D深度图像序列的基于滑动窗口的三维手指检测跟踪算法 (3dFDT) 。微软的Kinect被作为获取三维深度图像序列的摄像�
Sliding Window Protocol Implementatoin
TCP Sliding Window滑动窗口协议演示动画,Flash播放,可以调整参数
2. Pattern Sliding Window.zip
sliding_window算法的python版本,分享给有需要的人
一篇流数据分析方面的经典SCI论文,2013年发表的
滑动窗口协议解析
var slidingWindow = SlidingWindow ( alloc , free , options ) ; alloc是一个分配东西的函数。 它接收两个参数:第一个参数是要分配的块的index 。 第二个参数是一个可选参数,可以在move()第二个参数处传输。 ...
本文详细分析了基于滑动窗口的视觉slam或者视觉里程计方案的一致性问题
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
Sliding-window-topk.ppt
MATLAB典型代码 (示例面部检测结果来自anXDdd。) 项目4:带有滑动窗口的人脸检测 简短的 截止时间: 1月1日,晚上11:59。 所需文件:results / index.md和代码/ ...滑动窗口模型在概念上很简单:将所有图像块独立地...
sliding window and active constellation extension for fbmc oqam signal
Sliding Window:实现使用GBN协议和UDP进行通信的发送方和接收方 一点警告:这里发生了很多内存泄漏,因此克隆它修复并从中获得乐趣。 我有点想念的另一件事是解释滑动部分,它确实是分块完成的。
QSplitter实现伸缩滑动窗口,完整的代码,在centos6.6上测试运行过。