题外话
觉得自己真的太死板了，想一个做法就死磕，结果明明就不适合。
入门是看了其他语言的实现过程，明明我的语言并不适合这个方法，想用string来实现，然而string没有适合的函数，我却一直死磕，很简单的问题，磕了一上午，结果就是人磕自闭了。
真的感觉自己还是太笨了。
有什么办法呢，自闭完还是得冲。
至少用string学会了两个string函数的用法，比如clear()、
tmp.insert(tmp.end(),1,s[eptr])、
tmp.insert(tmp.end(),s.begin()+sptr,s.begin()+eptr);
正题：滑动窗口
概述
TCP协议中，数据的发送方和接收方都会使用滑动窗口来控制数据的收发。
它有以下优点：
滑动窗口的使用避免了数据重复校验，在字符串匹配等场合有多应用。
思路
- 设置左右指针，指向窗口的左端和右端
- 右指针向右移动
- 右指针变化的同时，如果满足条件，左指针移动，缩小窗口
例题
leetcode 3.无重复字符的最长字串
点击进入题目
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 lengthOfLongestSubstring(string s) {
int ans=0;
int n=s.size();
if(n==0) return 0;
if(n==1) return 1;
unordered_map<char, int> ss;
int sptr=0;
int eptr=0;
while(eptr<n){
char c1=s[eptr++];
ss[c1]++;
while(ss[c1]>1){
char c2=s[sptr];
ss[c2]--;
sptr++;
}
ans=max(ans,eptr-sptr);
}
return ans;
}
};
|
leetcode 220.存在重复元素Ⅲ
点击进入题目
思路：
set、滑动窗口
运用set内部排序的机制，滑动窗口主要就是要准确利用合适的数据结构；窗口就是边界的处理，内部所需要的东西，需要通过不同的数据结构来实现。
解析：
- eptr从小到大循环
- 窗口大小(即set.size())必须小于等于k，一旦比k大，左边界移一步（从set里擦除当前的sptr）
- 通过lower_bound()来找比nums[right]-t更大的数，如果找到了 就是true
- 如果循环完都没有找到，返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n=nums.size();
if(n==0||n==1) return false;
set<long >s1;
int sptr=0;
int eptr=0;
while(eptr<n){
if(eptr-sptr>k){
s1.erase(nums[sptr]);
sptr++;
}
if(s1.lower_bound((long long )nums[eptr]-t)!=s1.end()&&(*(s1.lower_bound((long long)nums[eptr]-t))-nums[eptr]<=t))
return true;
s1.insert(nums[eptr]);
eptr++;
}
return false;
}
};
|
59-I.滑动窗口的最大值
本来觉得自己挺行的，一看评论区，好吧，我是废物。
可以用双端队列。反正道理都差不多。
思路：
滑动窗口+multiset
用set有坑，因为窗口内会有重复的元素！！
用set的话，如果窗口的left是重复元素之一，erase(nums[left])的时候会擦掉窗口内的元素！
咱用mutiset（再夸一下，STL无敌！！），然而！multiset的erase也有误用情况！因为erase都是擦除全部，得用迭代器来找（不用多说，很好理解吧！），然后erase掉迭代器的位置。
解析：
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
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
multiset <int > tmp;
vector <int > ans;
int left=0;
int right=0;
int n=nums.size();
if(nums.size()==0) return ans;
while(right<n){
if(right-left>k){
multiset <int>::iterator pos = tmp.find(nums[left]);
tmp.erase(pos);
left++;
}
if(right-left==k){
int nn=tmp.size();
ans.push_back(*tmp.rbegin());
}
tmp.insert(nums[right]);
right++;
}
tmp.insert(nums[right-1]);
if(right-left>k){
multiset <int>::iterator pos = tmp.find(nums[left]);
tmp.erase(pos);
left++;
}
if(right-left==k){
int nn=tmp.size();
ans.push_back(*tmp.rbegin());
}
return ans;
}
};
|
