Peter算法小课堂—蠕动区间

蠕动区间

蠕动区间（尺取法、双游标）是一个经典的优化算法。

我们以毛毛虫🐛举例说明

具体的，我们看题目

例题

最小区间

 这一题，我们用暴力法，复杂度O(N^2)

先给出暴力法代码

int ans=n+1;
for(int tail=0;tail<n;tail++){int sum=0;for(int head=tail;head<n;head++){sum+=x[head];if(sum>=m){ans=min(ans,head+1-tail);break;}}
}
cout<<ans<<endl;

 我们看一下蠕动区间怎么写

上面有注释，大家看不明白就私信哦

收集三原色

这道题更难一点……

数据结构

string x[N];
map<string,int> cnt;
set<string> rgb;
rgb.insert("red");
rgb.insert("green");
rgb.insert("blue");

主体部分

int sum=0,ans=n+1;
int tail=0,head=0;
while(1){while(head<n&&sum<3){string color=x[head++];if(!rgb.count(color)) continue;++cnt[color];if(cnt[color]==1) sum++;}if(sum<3) break;ans=min(ans,head-tail);string color=x[tail++];if(!rgb.count(color)) continue;--cnt[color];if(cnt[color]==0) sum--;
}
cout<<ans<<endl;

希望这些对大家有用，三联，必回