Colorful Candies 题解 [at_abc210 C map离散化 滑动窗口]

• 题目：Colorful Candies
• 解析
• 参考源码

题目：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;	
}