听说你还不会滑动窗口?来一篇文章带你学会滑动窗口算法
【摘要】 无重复字符的最长子串这道题主要就是滑动窗口的思想,何为滑动窗口?其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!也是单调队列的经典应用把最左边的队列持续移出,保留其最大长度,维持这个最大长度的队列,即是题目解class Solution {public: i...
无重复字符的最长子串
这道题主要就是滑动窗口的思想,何为滑动窗口?
其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!也是单调队列的经典应用
把最左边的队列持续移出,保留其最大长度,维持这个最大长度的队列,即是题目解
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;//根据题目实例来特判一个
unordered_set<char> lookup;//在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序
int maxStr = 0;
int left = 0;
for(int i = 0; i < s.size(); i++){
while (lookup.find(s[i]) != lookup.end()){
lookup.erase(s[left]);
left ++;
}
maxStr = max(maxStr,i-left+1);
lookup.insert(s[i]);
}
return maxStr;
}
};
滑动窗口
#include<iostream>
using namespace std;
int h,t=-1;
const int N=1e6+10;
int a[N],q[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
if(h<=t && i-q[h]+1>k) h++;
while(h<=t && a[q[t]]>=a[i]) t--;
q[++t]=i;
if(i+1>=k) cout<<a[q[h]]<<' ';
}
cout<<endl;
h=0;t=-1;
for(int i=0;i<n;i++)
{
if(h<=t && i-q[h]+1>k) h++;
while(h<=t && a[q[t]]<=a[i]) t--;
q[++t]=i;
if(i+1>=k) cout<<a[q[h]]<<' ';
}
return 0;
}
滑动窗口的平均值
class MovingAverage {
private:
int len = 0;
queue<int> nums;
double sum = 0;
public:
MovingAverage(int size) {
len = size;
}
double next(int val) {
nums.push(val);
sum += val;
if (nums.size() > len) {
sum -= nums.front();
nums.pop();
}
return sum / nums.size();
}
};
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)