锐客网

  1. 首页 > it技术 > >

双指针|双指针 + 滑动窗口 寒假每日一题 品种邻近

题目：
农夫约翰的 N 头奶牛排成一排，每头奶牛都用其品种 ID 进行描述。
如果两头相同品种的牛靠得太近，它们就会吵架。
具体的说，如果同一品种的两头奶牛在队列中的位置相差不超过 K，我们就称这是一对拥挤的牛。
【双指针|双指针 + 滑动窗口 寒假每日一题 品种邻近】请计算品种 ID 最大的拥挤奶牛对的品种 ID。
输入格式 第一行包含两个整数 N 和 K。
接下来 N 行，每行包含一个整数表示队列中一头奶牛的品种 ID。
输出格式 输出品种 ID 最大的拥挤奶牛对的品种 ID。
如果不存在拥挤奶牛对，则输出 ?1。
数据范围 1≤N≤50000,
1≤K品种 ID 范围 [0,106]。

分析：这道题应该怎么考虑呢，首先我们要知道的是我们要去找的是拥挤奶牛对中品种ID最大的，这里有两个点：首先我们要去找最大，所以肯定要定义一个ans去取max ； 并且，我们要去找拥挤的奶牛，自然要让我们的双指针始终在一个“拥挤的状态下”；
至于为什么要用双指针，考虑到这是一个一眼看过来就是的滑动窗口问题，我们肯定要用双指针啊！
然后我们就考虑，我们在遍历这样的一个序列的时候是怎么样来分辨这个窗口中是否有拥挤奶牛对的，我们肯定不能对每一个窗口就拿一个去硬怼，所以我们会想到map的映射，也会想到单调队列的出队，我们提取其中重要的部分就是，每读入一个新元素，我们就要让它对应的映射值加一，如果这个映射值 == 2了，说明前面一定有一个同样的值出现，所以肯定新元素是拥挤的，我们就用max去判断；那么我们需要注意了，为了保证一定要在同一个窗口中，所以当窗口移动时，队首的点就要自觉离开，并将其映射值减一，以免产生影响；
所以我们开辟了一个cnt数组，但还要注意了，cnt数组的下标和arr的值时一一对应的，所以其范围要适配arr的值，要开到10^6以上！
综上，我们要熟悉这种做题方式！

    推荐阅读


    上一篇：给定class对象返回该类的实例

    下一篇：介绍一个文本语音神器，几行代码就能搞定！