0%

【每日一题】滑动窗口题解

题目链接

常规做法当然是单调队列,但我全都要。

单调队列

Solution

求最大值和最小值的方法实际上是一样的。

这里只以求最大值为例:

从左往右扫到某一个值的时候,如果当前值的大小比前面的某些值要大的时候,结尾是当前位置往右的的最大值就不可能是前面比当前值小的。

还有一种情况是队头已经超出这个区间范围了,这个时候就需要先把他给剔除。

于是构造一个单调队列,队头是值较大的一端,而队尾是值较小的一端,那么构造好每一个位置的单调队列后,单调队列的队头就是这个区间的最大值。

时间复杂度$O(n)$ 空间复杂度$O(n)$

Code

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
#include<bits/stdc++.h>
using namespace std;
vector<int> calc(vector<int> a, int k, bool isMin) {
const int n = a.size();
// 如果是求最小值,取负数做一遍求最大值的,然后再将结果取负数即可
if(isMin) for(int &x: a) x = -x;
deque<int> q; // 双端队列
vector<int> ret(n - k + 1); // 返回的数组
for(int i = 0; i < n; i++) {
while(!q.empty() && q.front() <= i - k) q.pop_front(); // 下标超出区间
// 构造出单调队列 将没有机会成为最大值的出队
while(!q.empty() && a[q.back()] < a[i]) q.pop_back();
q.push_back(i);
// 队头作为最大值
if(i + 1 >= k) ret[i + 1 - k] = a[q.front()];
}
if(isMin) for(int &x: ret) x = -x;
return ret;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
vector<int> a(n);
for(int &x: a) cin >> x;
vector<int> res = calc(a, k, true); // 计算各区间最小值
for(int i = 0; i < n - k + 1; i++) {
cout << res[i] << " \n"[i == n - k];
}
res = calc(a, k, false); // 计算各区间最大值
for(int i = 0; i < n - k + 1; i++) {
cout << res[i] << " \n"[i == n - k];
}
}

ST表

Solution

ST表可以$O(n\log(n))$预处理数组,然后可以$O(1)$询问每一个区间内的最大值或者是最小值。

那么就可以很轻松地MLE这一道题了。

怎么卡我内存啊!!算了一下发现确实不行。

下面代码只过了50%。

时间复杂度$O(n\log(n))$ 空间复杂度$O(n\log(n))$

Code

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
#include<bits/stdc++.h>
using namespace std;
// 建ST表
template<typename T>
struct ST {
vector<vector<pair<T, T>>> dp;
vector<int> lg;
// 预处理 O(nlog(n))
ST(const vector<T> &a) {
const int n = a.size(), m = 33 - __builtin_clz(n);
// 申请足够的空间 需要的空间有点多
dp = vector<vector<pair<T, T>>>(n + 1, vector<pair<T, T>>(m));
lg = vector<int> (n + 1, 0);
for(int i = 1; i <= n; i++) {
dp[i][0] = {a[i - 1], a[i - 1]}, lg[i] = lg[i >> 1] + 1;
}
for(int j = 1; (1 << j) <= n; j++) {
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
pair<T, T> &x = dp[i][j - 1], &y = dp[i + (1 << (j - 1))][j - 1];
dp[i][j] = {min(x.first, y.first), max(x.second, y.second)};
}
}
}
// 询问 O(1)
pair<T, T> minmax(int l, int r) {
l++, r++;
int k = lg[r - l + 1] - 1;
return {
min(dp[l][k].first, dp[r - (1 << k) + 1][k].first),
max(dp[l][k].second, dp[r - (1 << k) + 1][k].second)
};
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
vector<int> v(n);
for(int &x: v) cin >> x;
ST<int> obj(v);
vector<int> a1(n - k + 1), a2(n - k + 1);
for(int i = k - 1; i < n; i++) {
tie(a1[i - k + 1], a2[i - k + 1]) = obj.minmax(i - k + 1, i);
}
for(int i = 0; i < n - k + 1; i++) {
cout << a1[i] << " \n"[i == n - k];
}
for(int i = 0; i < n - k + 1; i++) {
cout << a2[i] << " \n"[i == n - k];
}
}

线段树

Solution

线段树就很强大了,相比于ST表还可以支持修改内存也只是$O(n)$,但是各种操作的复杂度都是$O(\log(n))$的而不是$O(1)$的。

建完线段树暴力就完事了。

可恶啊,最小值和最大值一起求还是会MLE。那只能分开来求,而且分开来求的话就不需要把答案存起来。

时间差点超了但是能过就行嘻嘻。

时间复杂度$O(n\log(n))$ 空间复杂度$O(n)$

Code

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
#include<bits/stdc++.h>
using namespace std;
#define lson i << 1, l, mid
#define rson i << 1 | 1, mid + 1, r
#define mid ((l + r) >> 1)
const int N = 1000000 + 10;
int b[N << 2], a[N];
// 线段树建树
void build(int i, int l, int r, bool is) {
if(l == r) { b[i] = a[l]; return; }
build(lson, is); build(rson, is);
if(is) b[i] = min(b[i << 1], b[i << 1 | 1]);
else b[i] = max(b[i << 1], b[i << 1 | 1]);
}
// 线段树查询
int query(int i, int l, int r, int L, int R, bool is) {
// 超出范围返回一个极限值
if(r < L || l > R) return is ? INT_MAX : INT_MIN;
if(L <= l && r <= R) return b[i];
if(is) return min(query(lson, L, R, is), query(rson, L, R, is));
else return max(query(lson, L, R, is), query(rson, L, R, is));
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n, true);
for(int i = k; i <= n; i++) {
cout << query(1, 1, n, i - k + 1, i, true) << " \n"[i == n];
}
build(1, 1, n, false); // 省点空间做build两次线段树
for(int i = k; i <= n; i++) {
cout << query(1, 1, n, i - k + 1, i, false) << " \n"[i == n];
}
}

回到开头