| 题目名称 | 495. [POJ 2823]滑动窗口 |
|---|---|
| 输入输出 | window.in/out |
| 难度等级 | ★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 9 |
| 题目来源 |
 cqw
于2010-11-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 查看题解 | 分享题解 |
| 通过：513， 提交：967， 通过率：53.05% | ||||
 史莱克音洛 |
100 | 0.363 s | 18.07 MiB | C++ |
 rsqppp |
100 | 0.422 s | 191.05 MiB | C++ |
 Bennettz |
100 | 0.433 s | 23.23 MiB | C++ |
 Tiny |
100 | 0.454 s | 91.75 MiB | C++ |
 Hyoi_0Koto |
100 | 0.489 s | 9.15 MiB | C++ |
 夜莺 |
100 | 0.490 s | 10.56 MiB | C++ |
 LGLJ |
100 | 0.510 s | 17.29 MiB | C++ |
 牧殇 |
100 | 0.514 s | 7.83 MiB | C++ |
 BeiYu |
100 | 0.514 s | 11.76 MiB | C++ |
|
BeiYu |
100 | 0.518 s | 11.76 MiB | C++ |
| 本题关联比赛 | |||
| 20101110 | |||
| Segment Tree Competition | |||
| 至少完成十道练习 | |||
| 数据结构练习 | |||
| 关于 滑动窗口 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
ST表慢死
| ||||
|
线段树咋写，求改正
| ||||
|
哈哈，暴力直接过!
时间1s不就行了？ | ||||
|
RMQ成功切掉了单调队列
| ||||
|
https://www.bilibili.com/video/av12492611/
 leon
2018-10-22 23:49
35楼
| ||||
|
回复 @Ezoi_Doge_OI再见 :
+1  +1s
2017-10-29 08:21
34楼
| ||||
|
水过刘明
| ||||
|
在poj死活过不去……
 Shirry
2017-10-16 09:05
32楼
| ||||
|
线段树果然慢
| ||||
|
是我写的姿势不对把。。。写的单调队列比线段树慢10倍
终于发现原因了，没有加读入优化 | ||||
cb
Hale
Hzoi_Mafia
kZime【问题描述】
给你一个长度为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。
【输入格式】
第一行，两个整数n，k。
第二行，n个整数。
【输出格式】
第一行每个位置的min value。
第二行每个位置的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。