Colorful Candies 题解 [at_abc210 C map离散化 滑动窗口]
题目：Colorful Candies
地址：at_abc210_c
解析
-
TAG: map离散化 滑动窗口
-
DESCRIPITION:
有一排不同色地蜡烛问你连续一个K大小地区间内有多少种颜色。 -
INPUT:
-
SOLUTION:
颜色很多，我们用map来记录当下颜色是否存在，然后简单的从左向右滑动窗口，减去离开窗口地颜色，加上进入窗口的颜色，同时更新颜色数量的最大值。反正很简单直接上代码：
参考源码
/*
其实我感觉这道题最大的意义还是熟悉了下map的使用（虽然这么说牵强了点）
比如说 m.erase()来移除键值对， m.count() 判断是否有键出现。
*/
#include<iostream>
#include<string>
#include<map>
using namespace std;
const int MAXN = 3e5;
map<int,int> m;
int nums[MAXN+10];
int c[MAXN+10];
int main()
{
int N,K;
//choose K consecutive candies
// i [1,N-K+1]
cin>>N>>K;
nums[N-K+1] = 0;
int ns = 0;
int maxx = 0;
for(int i=1;i<=N;i++){
cin>>c[i];
// 接下来对前K个蜡烛的颜色情况做个特殊处理方便接下来直接从K+1开始滑动窗口
if(i<=K){
if(m.count(c[i])==0){
m[c[i]]=1;
ns++;
//nums[N-K+1]++;
}
else{
m[c[i]]++;
}
}
}
maxx = ns;
for(int i=K+1;i<=N;i++){
m[c[i-K]]--; // 旧的蜡烛滑出一个
if(m[c[i-K]]==0){ // 这个颜色数量归零，去掉这个map映射
ns--;
m.erase(c[i-K]);
}
if(m.count(c[i])==0){ // 新的蜡烛滑入一个，并且这个颜色没有出现过，更新新map和答案最大值
m[c[i]]=1;
ns++;
if(ns>maxx) maxx = ns; // 只有出现新的颜色才有可能更新最大值
}
else{ // 新的蜡烛滑入一个，并且这个颜色出现过，直接该颜色数量+1
m[c[i]]++;
}
}
cout<<maxx<<endl;
return 0;
}