分析:题目要求满足性质:区间内不同类别的数量不超过k的 最长区间。所以假设固定左端点,右端点从左往右移动的过程中,性质是先满足,后不满足。即性质满足单调性 。一切满足单调性的问题都能用双指针解决。
如何维护上述性质:
1,我们对当前区间维护一个桶来记录每个值出现的次数(可以使用数组或者哈希表来实现)。
图书馆计划举办一场主题书展,需要在书架上选出一段连续摆放的书籍作为展品。书架上共有 N 本书,每本书都有一个类别编号(编号相同的书属于同一类别)。为了让展品的主题不至于过于分散,管理员要求所选连续书段中不同类别的数量不能超过 K 种,同时希望书段尽可能长,以展示更多馆藏。请你帮助管理员求出满足条件的最长连续书段的长度。
约束:N 和 K 均不超过 5000,每本书的类别编号为 1 到 2000 之间的整数。
第一行包含两个整数 N 和 K,分别表示书架上图书的总数和允许的不同类别数量的上限。 第二行包含 N 个整数,依次表示每本书的类别编号,相邻整数之间用一个空格分隔。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册