滑动窗口 /【模板】单调队列
题目描述
有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k = 3$，有如下过程：
输入格式
输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
样例 #1
样例输入 #1
样例输出 #1
1
2
| -1 -3 -3 -3 3 3
3 3 5 5 6 7
|
提示
【数据范围】
对于 $50%$ 的数据，$1 \le n \le 10^5$；
对于 $100%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。
题解
分析
- 按照大小排序，如果大小相同按照索引值进行排序，在推入超过窗口大小的数据时，判断顶部的数据是否在窗口内，如果不在即推出数据即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| import java.io.*;
import java.util.PriorityQueue;
public class P1886 {
static StreamTokenizer st = new StreamTokenizer(System.in);
static Writer pw = new BufferedWriter(new PrintWriter(System.out));
static int nextInt() throws IOException {
st.nextToken();
return (int) st.nval;
}
public static void main(String[] args) throws IOException {
int n = nextInt();
int k = nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = nextInt();
int[][] out = slidingWindow(arr, k);
for (int a : out[1]) pw.write(a + " ");
pw.write("\n");
for (int b : out[0]) pw.write(b + " ");
pw.close();
}
static int[][] slidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> max = new PriorityQueue<>((pair1, pair2) -> (pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]));
PriorityQueue<int[]> min = new PriorityQueue<>((pair1, pair2) -> -(pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]));
for (int i = 0; i < k; ++i) {
max.offer(new int[]{nums[i], i});
min.offer(new int[]{nums[i], i});
}
int[][] ans = new int[2][n - k + 1];
ans[0][0] = max.peek()[0];
ans[1][0] = min.peek()[0];
int index = 1;
for (int i = k; i < n; ++i) {
max.offer(new int[]{nums[i], i});
min.offer(new int[]{nums[i], i});
while (max.peek()[1] <= i - k) {
max.poll();
}
while (min.peek()[1] <= i - k) {
min.poll();
}
ans[0][index] = max.peek()[0];
ans[1][index] = min.peek()[0];
index++;
}
return ans;
}
}
|
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
|
