塔子哥是一名设计师,最近接到了一项重要任务:设计一个新款的生日蜡烛,以庆祝公司成立20周年。为了使蜡烛看起来更加炫目,塔子哥计划在蜡烛上缠绕彩带。他买了一串长度为 N 的非常漂亮的彩带,每一厘米的彩带上都是一种色彩,但是当他拿到彩带后才发现,彩带上的颜色太多了,超出了他设计中所需要的颜色种类数量。
分析:题目要求满足性质:区间内颜色种类不超过k的 最长区间。所以假设固定左端点,右端点从左往右移动的过程中,性质是先满足,后不满足。即性质满足单调性 。一切满足单调性的问题都能用双指针解决。
如何维护上述性质:
1,我们对当前区间维护一个桶来记录每个值出现的次数(可以使用数组或者哈希表来实现)。
扫码备注加群即可,期待您的到来~