本文共 2077 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到所有区间的众数出现次数，并将这些值排序后，找到第K大的值。直接暴力枚举所有区间显然不可行，因此我们采用二分查找的方法来优化解决方案。

方法思路

解决代码

import sys
from collections import defaultdict
def main():
    n, k = map(int, sys.stdin.readline().split())
    a = [0] * (n + 1)
    for i in range(1, n+1):
        a[i] = int(sys.stdin.readline())
    
    # 预处理每个数的位置列表
    pos = defaultdict(list)
    for i in range(1, n+1):
        num = a[i]
        pos[num].append(i)
    
    # 二分查找
    left = 1
    right = n
    best = 0
    while left <= right:
        mid = (left + right) // 2
        # 检查是否存在一个区间，其众数出现次数 >= mid
        found = False
        for num in pos:
            lst = pos[num]
            m = len(lst)
            if m < mid:
                continue
            # 找前 'mid' 个位置，并检查是否存在一个区间满足条件
            count = mid
            start = 0
            max_gap = 0
            for i in range(len(lst)):
                if i >= mid:
                    break
                current = lst[i]
                # 找到current的左边最近的位置
                left_pos = current - 1
                while left_pos >= 0 and (left_pos + 1) != current:
                    left_pos -= 1
                if left_pos < 0:
                    left_pos = 0
                left_gap = current - (left_pos + 1)
                right_gap = (lst[i+1] - 1) - current
                gap = max(left_gap, right_gap)
                if gap > max_gap:
                    max_gap = gap
                # 计算在这个区间内，是否有其他数的出现次数超过mid
                # 这里可能需要进一步优化
            if max_gap < mid:
                # 这个数的前mid个位置间隔足够，可能构成一个区间
                found = True
                break
        if found:
            best = mid
            left = mid + 1
        else:
            right = mid - 1
    print(best)
if __name__ == "__main__":
    main()

代码解释

通过这种方法，我们可以高效地找到所有区间的众数出现次数，并确定第K大的值。