定长滑动窗口适合窗口长度固定的题目，核心是把每轮操作稳定拆成“入、更新、出”。
定长滑动窗口：每一轮先纳入右端点，再在窗口形成后更新答案，最后移出左端点。 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
| class Solution {
public:
int maxVowels(string s, int k) {
int ans = 0;
int tmp = 0;
for (int i = 0; s[i] != '\0'; i++) {
//入
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u') {
tmp++;
}
//更新
if (tmp > ans)
ans = tmp;
//出
int l = i - k + 1;
if (l >= 0) {
if (s[l] == 'a' || s[l] == 'e' || s[l] == 'i' || s[l] == 'o' ||
s[l] == 'u') {
tmp--;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double tmp = 0;
double ans = -1e10;
int n = nums.size();
for(int i=0; i<n; i++){
//入
tmp += nums[i];
int l = i - k + 1;
//更新
if(l >= 0 && tmp > ans) ans = tmp;
//出
if(l >= 0) tmp -= nums[l];
}
ans /= (1.0 * k);
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
| class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int sum = 0;
int ans = 0;
int t = threshold * k;
int n = arr.size();
for(int i=0; i<n; i++){
//入
sum += arr[i];
int l = i - k + 1;
if(l >= 0){
//更新答案
if(sum >= t) ans++;
//出
sum -= arr[l];
}
}
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
26
27
28
29
30
31
32
33
| class Solution {
public:
vector<int> getAverages(vector<int>& nums, int k) {
vector<int> ans;
int n = nums.size();
for(int i=0; i<min(n, k); i++){
ans.push_back(-1);
}
long long sum = 0;
for(int i=0; i<min(n, k); i++){
sum += nums[i];
}
for(int i=k; i<n; i++){
//入
sum += nums[i];
int l = i - 2 * k;
//更新
if(l >= 0) ans.push_back(sum / (2 * k + 1));
//出
if(l >= 0) sum -= nums[l];
}
while(ans.size() < n){
ans.push_back(-1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int minimumRecolors(string blocks, int k) {
int ans = 0x3f3f3f3f;
int op = 0;
int n = blocks.length();
for(int i=0; i<n; i++){
//入
if(blocks[i] == 'W') op++;
int l = i - k + 1;
if(l < 0) continue;
//更新
ans = min(ans, op);
//出
if(blocks[l] == 'W') op--;
}
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
26
27
28
29
30
31
32
| class Solution {
public:
long long maxSum(vector<int>& nums, int m, int k) {
unordered_map<long long, int> map;
long long sum = 0;
long long ans = 0;
int n = nums.size();
for(int i=0; i<n; i++){
//入
map[nums[i]]++;
sum += nums[i];
int l = i - k + 1;
if(l < 0) continue;
//更新
if(map.size() >= m){
ans = max(ans, sum);
}
//出
map[nums[l]]--;
if(map[nums[l]] == 0) map.erase(nums[l]);
sum -= nums[l];
}
return ans;
}
};
/*
1.这一题刚开始用set.size检查唯一元素个数，但在“出”的阶段出现问题，因为set无法得知元素重复
个数，进而不能确定nums[l]是否应该从set中删去。用unordered_map记录元素出现次数即可。
2. 一开始没考虑数据范围，没开long long
*/
|
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
| class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
long long ans = 0;
unordered_map<int, int> m;
long long sum = 0;
int n = nums.size();
for(int i=0; i<n; i++){
//入
sum += nums[i];
m[nums[i]]++;
int l = i - k + 1;
if(l < 0) continue;
//更新
if(m.size() == k) ans = max(ans, sum);
//出
sum -= nums[l];
m[nums[l]]--;
if(m[nums[l]] == 0) m.erase(nums[l]);
}
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
26
27
28
29
30
31
| class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int total = 0;
int ans = 0x3f3f3f3f;
int sum = 0;
int n = cardPoints.size();
//原问题等价于选出点数和最小的连续n-k张牌
for(int i=0; i<n; i++){
total += cardPoints[i];
//入
sum += cardPoints[i];
//更新
int l = i - (n - k) + 1;
if(l < 0) continue;
ans = min(ans, sum);
//出
sum -= cardPoints[l];
}
//n-k == 0时，区间长为0，无法用滑动窗口
if(k == n) ans = total;
else ans = total - ans;
return ans;
}
};
/*
这一题一开始的思路是从n-k的位置遍历到k的位置，用滑动窗口求最大和，但区间左端很难处理，卡了。
将问题转换后就很好求了。
*/
|
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
| class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int sum[2]; //sum[0] 表示 grumpy[i] 为 0 时的和, sum[1] 同理
int maxSum1 = -1;
int n = customers.size();
for(int i=0; i<n; i++){
//入
sum[grumpy[i]] += customers[i];
//更新
int l = i - minutes + 1;
if(l < 0) continue;
maxSum1 = max(maxSum1, sum[1]);
//出
if(grumpy[l]) sum[1] -= customers[l];
}
return sum[0] + maxSum1;
}
};
/*
一开始没有拆解清楚问题，没有什么思路。用O(n^2)过了。
实际上，只需要分开grumpy为0和1的情况即可：
1.grumpy为0，直接加
2.grumpy为1，用滑动窗口算出窗口内最大和
结果为二者相加
*/
|
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
| //用右端点
class Solution {
public:
vector<int> decrypt(vector<int>& code, int k) {
int n = code.size();
vector<int> ans(n);
int r = k > 0 ? k + 1 : n;
k = abs(k);
int s = reduce(code.begin() + r - k, code.begin() + r, 0);
/*
reduce 计算左闭右开区间累加和，初始值为0（第三个参数）
*/
for(int i=0; i<n; i++){
ans[i] = s;
s += code[r % n] - code[(r - k) % n];
r++;
}
return ans;
}
};
//用左端点
class Solution {
public:
vector<int> decrypt(vector<int>& code, int k) {
int n = code.size();
vector<int> ans(n);
int l = k > 0 ? 1 : n + k;
k = abs(k);
int s = reduce(code.begin() + l, code.begin() + l + k, 0);
for(int i=0; i<n; i++){
ans[i] = s;
s += code[(l + k) % n] - code[l % n];
l++;
}
return ans;
}
};
|
