序言
滑动窗口一直以来都是我不曾注意到的，直到上班之后和同事聊天的时候才知道有这么个算法。恰巧最近做题的时候经常碰到，就专门整理一下。
本文的题目全都来自LeetCode，题单则是来自灵茶山艾府的题集
最后一题没做，因为我没看懂题目。
题解和代码
题目分析
题目要求最大元素处于[left, right]之间，这就意味着，如果nums[i] > right，那么nums[i]所在的子数组都是不符合条件的，就都得去掉，由此可以看出，大于right的元素都是用来分隔的。
第二，如果nums[i] < left，那么nums[i]自身是不可以作为一个独立的子数组的。
分析示例2：由于9大于right(8)，所以9把数组分成了两个部分，且互不干扰。分别是[2]和[2, 5, 6]
对于[2]，有且仅有一个元素，对于[2, 5, 6]，则是[2], [2, 5], [2, 5, 6], [5], [5, 6], [6]共6个子数组。
可以思考一下，如果[2, 5, 6]再加一个7，会多出多少个解呢，答案是以6结尾的数组加上单独的7，一共是4个。
以6结尾的数组，肯定是6之前的元素数量，也就是数组长度了。同理，对于处于[left, right]之间的元素，我们的规律已经找到了。
如果新增的不是7，而是1呢，很显然，1不能独立作为一个子数组，所以新增的是三个解
如果再次新增一个1，变为[2, 5, 6, 1, 1]，那么第二个1可以新增多少个解呢，答案也是3个，因为比left小的元素，不能作为独立的子数组，所以必须依赖最后一次出现的处于[left, right]中的元素。
代码实现
展开代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int n = nums.size();
int ans = 0, l = 0, r = -1;
for (int i = 0; i < n; i++) {
if (nums[i] > right) l = i + 1;
if (nums[i] >= left) r = i;
ans += r - l + 1;
}
return ans;
}
};
|
最后贴一下战绩： 
题目分析
题目的意思是可以从数组首尾任选一个数，使得选中的数恰好等于x。
按照题目的意思来肯定不好做，但是我们可以反过来，从数组当中去掉一个子数组，使得子数组的和恰好等于，sum(nums) - x。 所以这个就恰好无缝衔接到了滑动窗口。
代码实现
展开代码
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
|
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int n = nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum < x) return -1;
if (sum == x) return n;
int ans = -1;
int target = sum - x;
int left = 0, right = 0;
int index = 0;
int cur_sum = 0;
while (true) {
while (cur_sum < target && index < n) {
cur_sum += nums[index];
index++;
}
do {
if (cur_sum == target) ans = max(ans, index - left);
cur_sum -= nums[left];
left++;
} while (cur_sum >= target && left < index);
if (index >= n) break;
}
return ans == -1 ? -1 : n - ans;
}
};
|
贴战绩: 
题目分析
这个题目还是比较简单的，QWER本来的比例是相等的，如果有字母多了，那就必然有字母少了，我们只需要找到一段子串，至少包含多出来的那些字母就行了。
代码实现
展开代码
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
|
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int balancedString(string s) {
int n = s.length();
int type[128] = {0};
type['Q'] = 0;
type['W'] = 1;
type['E'] = 2;
type['R'] = 3;
int cnt[4] = {0};
int cnt_now[4] = {0};
int c = 0;
for (int i = 0; i < n; i++) {
c = type[s[i]];
cnt[c]++;
}
vector<int> overChars(4, 0);
int len_over = 0;
for (int i = 0; i < 4; i++) {
c = i;
if (cnt[c] > (n / 4)) {
overChars[c] = cnt[c] - (n / 4);
len_over++;
}
}
if (len_over == 0) return 0;
int left = 0, right = 0, res = n;
int over_cnt = 0;
while (right < n) {
while (right < n && over_cnt < len_over) {
c = type[s[right]];
cnt_now[c]++;
if (cnt_now[c] == overChars[c]) {
over_cnt++;
}
right++;
}
while (left < n && over_cnt == len_over) {
res = min(res, right - left);
c = type[s[left]];
cnt_now[c]--;
if (cnt_now[c] == overChars[c] - 1) {
over_cnt--;
}
left++;
}
}
return res;
}
};
|
贴战绩: 
题目分析
题目要求我们找到一个子数组，删除它之后，剩余数组仍然有序。对于这个题目来说，如果有多段有序子数组的话，其实中间的都是要删掉的，我们的目标仅仅是把一头一尾拼接起来。
因为中间的段落一定会是在第一段最后的数要小的那个数之后的，所以不满足。同理和最后一段最开始的数相比也是，所以中间的都得删掉。我们就只需要比较一头一尾两段即可。
代码实现
展开代码
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
|
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& arr) {
int n = arr.size();
int left = 0, right = n - 1, ans = n - 1;
for (int i = n - 2; i >= 0; i--) {
if (arr[i] <= arr[i + 1]) {
right = i;
}
else {
break;
}
}
if (right == 0) return 0;
ans = right;
for (int i = 0; i < n; i++) {
left = i;
while (right < n && arr[left] > arr[right]) {
right++;
}
ans = min(ans, right - left - 1);
if (i == n - 1 || arr[i] > arr[i + 1]) {
break;
}
}
return ans;
}
};
|
贴战绩: 
题目分析
题目要求我们能采摘的果子下标是有范围的，就是[startPos - k, startPos + k]
如果我们要采摘从[l, r]的果子，我们会用到多少步数，可以分情况讨论:
如果l和r在同一侧，就是max(abs(r - startPos), abs(startPos - l))
如果l和r在不同侧，就是r - l + min(abs(r - startPos), abs(startPos - l))
代码实现
展开代码
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
|
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int n = fruits.size();
int left = -1;
int right = -1;
for (int i = 0; i < n; i++) {
if (fruits[i][0] >= startPos - k && left == -1) left = i;
if (fruits[i][0] <= startPos + k) right = i;
}
int l = left;
int r = left;
if (left == -1 || right == -1) return 0;
int ans = 0;
int nowStep = 0;
int nowFruits = 0;
int li = 0;
int ri = 0;
while (r <= right) {
while (r <= right && nowStep <= k) {
li = fruits[l][0];
ri = fruits[r][0];
if (ri <= startPos && li <= startPos || ri >= startPos && li >= startPos) {
nowStep = max(abs(ri - startPos), abs(startPos - li));
}
else {
nowStep = ri - li + min(abs(ri - startPos), abs(startPos - li));
}
nowFruits += fruits[r][1];
r++;
if (nowStep > k) break;
ans = max(ans, nowFruits);
}
while (l <= right && nowStep > k) {
li = fruits[l + 1][0];
ri = fruits[r - 1][0];
if (ri <= startPos && li <= startPos || ri >= startPos && li >= startPos) {
nowStep = max(abs(ri - startPos), abs(startPos - li));
}
else {
nowStep = ri - li + min(abs(ri - startPos), abs(startPos - li));
}
nowFruits -= fruits[l][1];
l++;
if (nowStep <= k) {
ans = max(ans, nowFruits);
break;
}
}
}
return ans;
}
};
|
贴战绩: 
