滑动窗口
定长滑动窗口：窗口的大小是固定不变的。如果要求一个定长窗口内某一些数据的最大值或者最小值，可以通过维护单调递增或者递减的队列来解答。
不定长滑动窗口：窗口的大小是不定的，可以更改。这时候经常会配合双指针来解答。
例题：
思路：
这是定长的一维滑动窗口。因为可以随机从序列中取值，所以可以对序列的顺序进行操作。要求长度为k的序列最大差值和最小差值乘积的最小值。
可以先对序列进行排序操作，这样子在取序列差值最大值的时候就可以用长度为k的序列两侧的元素进行相减操作。
然后维护一个双端队列，存储元素的下标，保证队列中下标对应元素和他的下一位元素相减的差值从前向后递增，并且后面元素的下标一定大于前面的元素：依次遍历元素下标，当元素下标小于k时，这时序列的长度小于k，所以只往双端队列中添加元素。当时元素下标大于k时，需要判断双端队列最前面的元素是否还在队列中，如果没有存在则去掉，。
AC代码：
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
| import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int count = scan.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}
Arrays.sort(nums);
Deque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < count - 1; i++) {
int val = nums[i + 1] - nums[i];
while (!deque.isEmpty() && nums[deque.peekLast() + 1] - nums[deque.peekLast()] >= val) {
deque.pollLast();
}
deque.offerLast(i);
}
long res = (nums[deque.peekFirst() + 1] - nums[deque.peekFirst()]) * (long) (nums[count - 1] - nums[0]);
for(int i = count - 1; i < n - 1; i++) {
if(i + 1 - count == deque.peekFirst()) {
deque.pollFirst();
}
int val = nums[i + 1] - nums[i];
while (!deque.isEmpty() && nums[deque.peekLast() + 1] - nums[deque.peekLast()] >= val) {
deque.pollLast();
}
deque.offerLast(i);
res = Math.min(res, (nums[deque.peekFirst() + 1] - nums[deque.peekFirst()]) * (long) (nums[i + 1] - nums[i - count + 2]));
}
System.out.println(res);
}
}
|
思路：
这是定长的二维滑动窗口。要求n乘n矩阵内最大值和最小值之差最小，可以对每一行的元素进行操作，再对每一列的元素进行操作。
先对每一行的元素求长度为n的窗口内最大值和最小值：因为要求最大和最小，所以开了两个双端队列，进行和上一个题差不多的操作，开了一个三维数组来存储每一行的最大值和最小值，最后一维下标为0时是最大值，为1时是最小值。
再对每一列的元素求三维数组中长度为n的窗口的最大值和最小值。因为三维数组存储的是每一行长度为n的窗口最大值和最小值，所以这个操作就相当于求一个个nxn矩阵的最大值和最小值，直接相减取最小。
AC代码：
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
int n = scan.nextInt();
int[][] nums = new int[a][b];
int[][][] p = new int[a][b - n + 1][2];
for(int i = 0; i < a; i++) {
for(int j = 0; j < b; j++) {
nums[i][j] = scan.nextInt();
}
}
Deque<Integer> big = new ArrayDeque<>();
Deque<Integer> small = new ArrayDeque<>();
for(int i = 0; i < a; i++) {
big.clear();
small.clear();
for(int j = 0; j < n; j++) {
while (!big.isEmpty() && nums[i][big.peekLast()] <= nums[i][j]) {
big.pollLast();
}
big.offerLast(j);
while (!small.isEmpty() && nums[i][small.peekLast()] >= nums[i][j]) {
small.pollLast();
}
small.offerLast(j);
}
p[i][0][0] = nums[i][small.peekFirst()];
p[i][0][1] = nums[i][big.peekFirst()];
for(int j = n; j < b; j++) {
if(big.peekFirst() == j - n) {
big.pollFirst();
}
while (!big.isEmpty() && nums[i][big.peekLast()] <= nums[i][j]) {
big.pollLast();
}
big.offerLast(j);
if(small.peekFirst() == j - n) {
small.pollFirst();
}
while (!small.isEmpty() && nums[i][small.peekLast()] >= nums[i][j]) {
small.pollLast();
}
small.offerLast(j);
p[i][j - n + 1][0] = nums[i][small.peekFirst()];
p[i][j - n + 1][1] = nums[i][big.peekFirst()];
}
}
int res = Integer.MAX_VALUE;
for(int i = 0; i < b - n + 1; i++) {
big.clear();
small.clear();
for(int j = 0; j < n; j++) {
while (!big.isEmpty() && p[big.peekLast()][i][1] <= p[j][i][1]) {
big.pollLast();
}
big.offerLast(j);
while (!small.isEmpty() && p[small.peekLast()][i][0] >= p[j][i][0]) {
small.pollLast();
}
small.offerLast(j);
}
res = Math.min(p[big.peekFirst()][i][1] - p[small.peekFirst()][i][0], res);
for(int j = n; j < a; j++) {
if(big.peekFirst() == j - n) {
big.pollFirst();
}
while (!big.isEmpty() && p[big.peekLast()][i][1] <= p[j][i][1]) {
big.pollLast();
}
big.offerLast(j);
if(small.peekFirst() == j - n) {
small.pollFirst();
}
while (!small.isEmpty() && p[small.peekLast()][i][0] >= p[j][i][0]) {
small.pollLast();
}
small.offerLast(j);
res = Math.min(p[big.peekFirst()][i][1] - p[small.peekFirst()][i][0], res);
}
}
System.out.println(res);
}
}
|
思路：
这是定长的三维滑动窗口，和上面两个题思路相似。分别对长、宽、高进行操作，第一次相当于求长度为n的线性序列最大值和最小值，第二次操作相当于是一个个nxn的矩阵最大值和最小值，第三次操作相当于nxnxn的立方体最大值和最小值。和上个题不同的是这次我开了两个三维数组分别存最大值和最小值，方便区分。
AC代码：
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
int c = scan.nextInt();
int n = scan.nextInt();
int[][][] nums = new int[a][b][c];
for(int i = 0; i < c; i++) {
for(int j = 0; j < a; j++) {
for(int k = 0; k < b; k++) {
nums[j][k][i] = scan.nextInt();
}
}
}
int[][][] max1 = new int[a][b][c - n + 1];
int[][][] min1 = new int[a][b][c - n + 1];
Deque<Integer> max = new ArrayDeque<>();
Deque<Integer> min = new ArrayDeque<>();
for(int i = 0; i < a; i++) {
for(int j = 0; j < b; j++) {
max.clear();
min.clear();
for(int k = 0; k < c; k++) {
while (!max.isEmpty() && nums[i][j][max.getLast()] <= nums[i][j][k]) {
max.pollLast();
}
while (!min.isEmpty() && nums[i][j][min.getLast()] >= nums[i][j][k]) {
min.pollLast();
}
max.offerLast(k);
min.offerLast(k);
if(k >= n) {
if(k - n == max.peekFirst()) {
max.pollFirst();
}
if(k - n == min.peekFirst()) {
min.pollFirst();
}
}
if(k >= n - 1) {
max1[i][j][k - n + 1] = nums[i][j][max.peekFirst()];
min1[i][j][k - n + 1] = nums[i][j][min.peekFirst()];
}
}
}
}
c = c - n + 1;
int[][][] max2 = new int[a][b - n + 1][c];
int[][][] min2 = new int[a][b - n + 1][c];
for(int i = 0; i < a; i++) {
for(int k = 0; k < c; k++) {
max.clear();
min.clear();
for(int j = 0; j < b; j++) {
while (!max.isEmpty() && max1[i][max.getLast()][k] <= max1[i][j][k]) {
max.pollLast();
}
while (!min.isEmpty() && min1[i][min.getLast()][k] >= min1[i][j][k]) {
min.pollLast();
}
max.offerLast(j);
min.offerLast(j);
if(j >= n) {
if(j - n == max.peekFirst()) {
max.pollFirst();
}
if(j - n == min.peekFirst()) {
min.pollFirst();
}
}
if(j >= n - 1) {
max2[i][j - n + 1][k] = max1[i][max.peekFirst()][k];
min2[i][j - n + 1][k] = min1[i][min.peekFirst()][k];
}
}
}
}
b = b - n + 1;
long res = 0;
long M = (long) (1e9) + 7;
for(int j = 0; j < b; j++) {
for(int k = 0; k < c; k++) {
max.clear();
min.clear();
for(int i = 0; i < a; i++) {
while (!max.isEmpty() && max2[max.getLast()][j][k] <= max2[i][j][k]) {
max.pollLast();
}
while (!min.isEmpty() && min2[min.getLast()][j][k] >= min2[i][j][k]) {
min.pollLast();
}
max.offerLast(i);
min.offerLast(i);
if(i >= n) {
if(i - n == max.peekFirst()) {
max.pollFirst();
}
if(i - n == min.peekFirst()) {
min.pollFirst();
}
}
if(i >= n - 1) {
res = (res + (min2[min.peekFirst()][j][k]) - max2[max.peekFirst()][j][k] + M ) % M;
}
}
}
}
System.out.println(res);
}
}
|
思路：
这是一个不定长的滑动窗口。和上面不同的是，这次加了双指针的方法。
首先对w数组和d数组求前缀和。这样子w[i] - w[j]就相当于i到j后面一个元素内所有元素之和。
开两个指针，i和j，不断移动i指针，当存在j指针可以使w[i] - w[j]大于等于W时，不断移动j指针，同时存储0到j指针内的最小前缀和，i指针在的位置到0的前缀和减去j指针内的最小前缀和相当于以i为结尾的序列内能达到饱和的最大得分。
AC代码：
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
| import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int k = Integer.parseInt(s[1]);
long[] w = new long[n + 1];
long[] d = new long[n + 1];
w[0] = 0;
d[0] = 0;
String[] s1 = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
w[i] = Long.parseLong(s1[i - 1]);
w[i] += w[i - 1];
}
String[] s2 = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
d[i] = Long.parseLong(s2[i - 1]);
d[i] += d[i - 1];
}
long res = Long.MIN_VALUE;
int j = 0;
long min = Long.MAX_VALUE;
for(int i = 1; i <= n; i++) {
while (w[i] - w[j] >= k) {
min = Math.min(min, d[j]);
j++;
}
if(min != Long.MAX_VALUE) {
res = Math.max(d[i] - min, res);
}
}
System.out.println(res);
}
}
|
