Time Limit: 12000MS | Memory Limit: 65536K | |
Total Submissions: 53676 | Accepted: 15399 | |
Case Time Limit: 5000MS |
Description
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
Window position | Minimum value | Maximum value |
---|---|---|
[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
Output
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的数组,一个长为K的滑动的窗体从最左移至最右端,你只能见到窗口的K个数,每次窗体向右移动一位,如下表:
Window position | Min value | Max value |
[ 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 |
你的任务是找出窗口在各位置时的max value, min value.
第1行n,k,第2行为长度为n的数组
2行
第1行每个位置的min value
第2行每个位置的max value
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围:20%: n<=500; 50%: n<=100000;100%: n<=1000000;
分类标签 Tags 点此展开

2017-03-27
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e6+;
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,a[N],q[N],id[N];
int main(){
n=read();m=read();
for(int i=;i<=n;i++) a[i]=read();
int h=,t=;
for(int i=;i<m;i++){
while(h<t&&i-id[h]>=m) h++;
while(h<t&&q[t-]>a[i]) t--;
q[t]=a[i];id[t++]=i;
}
for(int i=m;i<=n;i++){
while(h<t&&i-id[h]>=m) h++;
while(h<t&&q[t-]>a[i]) t--;
q[t]=a[i];id[t++]=i;
if(h<t) printf("%d ",q[h]);
}
putchar('\n');
h=,t=;
for(int i=;i<m;i++){
while(h<t&&i-id[h]>=m) h++;
while(h<t&&q[t-]<a[i]) t--;
q[t]=a[i];id[t++]=i;
}
for(int i=m;i<=n;i++){
while(h<t&&i-id[h]>=m) h++;
while(h<t&&q[t-]<a[i]) t--;
q[t]=a[i];id[t++]=i;
if(h<t) printf("%d ",q[h]);
}
return ;
}
#include<cstdio>
using namespace std;
inline int read(){
register int x=;bool f=;
register char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return f?x:-x;
}
const int N=1e6+;
int n,k,a[N],num[N],q[N];
int main(){
n=read();k=read();
for(int i=;i<=n;i++) a[i]=read();
int l=,r=;
for(int i=;i<k;i++){
for(;l<=r&&i-num[l]>=k;l++);
for(;l<=r&&a[i]<q[r];r--);
q[++r]=a[i];num[r]=i;
}
for(int i=k;i<=n;i++){
for(;l<=r&&i-num[l]>=k;l++);
for(;l<=r&&a[i]<q[r];r--);
q[++r]=a[i];num[r]=i;
printf("%d ",q[l]);
}
putchar('\n');
l=,r=;
for(int i=;i<k;i++){
for(;l<=r&&i-num[l]>=k;l++);
for(;l<=r&&a[i]>q[r];r--);
q[++r]=a[i];num[r]=i;
}
for(int i=k;i<=n;i++){
for(;l<=r&&i-num[l]>=k;l++);
for(;l<=r&&a[i]>q[r];r--);
q[++r]=a[i];num[r]=i;
printf("%d ",q[l]);
}
return ;
}
codevs4373 窗口==poj2823 Sliding Window的更多相关文章
-
POJ2823 Sliding Window (单调队列)
POJ2823 Sliding Window Time Limit: 12000MS Memory Limit: 65536K Total Submissions: 38342 Accepte ...
-
滑动窗口(Sliding Window)技巧总结
什么是滑动窗口(Sliding Window) The Sliding Problem contains a sliding window which is a sub – list that run ...
-
[Swift]LeetCode239. 滑动窗口最大值 | Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the a ...
-
数据流滑动窗口平均值 &#183; sliding window average from data stream
[抄题]: 给出一串整数流和窗口大小,计算滑动窗口中所有整数的平均值. MovingAverage m = new MovingAverage(3); m.next(1) = 1 // 返回 1.00 ...
-
【LeetCode】480. 滑动窗口中位数 Sliding Window Median(C++)
作者: 负雪明烛 id: fuxuemingzhu 公众号: 每日算法题 本文关键词:LeetCode,力扣,算法,算法题,滑动窗口,中位数,multiset,刷题群 目录 题目描述 题目大意 解题方 ...
-
POJ2823 Sliding Window
Time Limit: 12000MS Memory Limit: 65536K Total Submissions: 53086 Accepted: 15227 Case Time Limi ...
-
POJ2823 Sliding Window(单调队列)
单调队列,我用deque维护.这道题不难写,我第二次写单调队列,1次AC. -------------------------------------------------------------- ...
-
[POJ2823]Sliding Window 滑动窗口(单调队列)
题意 刚学单调队列的时候做过 现在重新做一次 一个很经典的题目 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗 ...
-
poj2823 Sliding Window luogu1886 滑动窗口 单调队列
模板题 #include <iostream> #include <cstring> #include <cstdio> using namespace std; ...
随机推荐
-
为什么mysql设置了密码之后,本地还可以直接访问,不需要输入密码就可以登录数据库了?
应为数据库里面有空用户 select * from mysql.user where user=''; 查询如果有,把他删了然后重启mysql服务. 他有空用户你删除了 然后重启mysql生效,这个是 ...
-
accept()
在一个套接口接受一个连接.accept()是c语言中网络编程的重要的函数,windows系统在#include<winsock.h> ,而linux系统在#include <sys/ ...
-
ElasticSearch已经配置好ik分词和mmseg分词(转)
ElasticSearch是一个基于Lucene构建的开源,分布式,RESTful搜索引擎.设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便.支持通过HTTP使用JSON进行数据索引 ...
-
phpcms 无法显示缩略图 Call to undefined function image_type_to_extension
问题背景: 线下的phpcms项目没问题,线上的phpcms新添加的图片缩略图显示有问题,查看了一下php版本,线下是5.5的,线上的是5.1的 问题原因: 看了一下线上的错误日志,显示: PHP F ...
-
Linux环境中DISPLAY环境变量的解释及设置
在Linux/Unix类操作系统上的GUI应用程序使用X Window系统(X Window System),它旨在允许多个用户使用窗口化的应用程序通过网络访问计算机. DISPLAY环境变量用来设置 ...
-
save与 merge与 saveOrUpdate的区别
save()方法很显然是执行保存操作的,如果是对一个新的刚new出来的对象进行保存,自然要使用这个方法了,数据库中没有这个对象. update()如果是对一个已经存在的托管对象进行更新那么肯定是要使用 ...
-
Oracle-11g 基于 NBU 的 rman 冷备份及恢复
html,body { font-size: 15px } body { font-family: Helvetica, "Hiragino Sans GB", "微软雅 ...
-
Python安装与环境变量的配置
python下载: Python安装包下载地址:http://www.python.org/ 根据实际的操作系统,安装合适的安装版本. Python安装: 本文以python 2.7.8(64位)为例 ...
-
Debate CodeForces - 1070F (贪心)
Elections in Berland are coming. There are only two candidates — Alice and Bob. The main Berland TV ...
-
java----JSTL学习笔记(转)
Java容器类包含List.ArrayList.Vector及map.HashTable.HashMap.Hashset ArrayList和HashMap是异步的,Vector和HashTable是 ...