题解：瑞学堂 瑞瑞的环形花坛

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

瑞学堂：瑞瑞的环形花坛

【题目描述】

瑞瑞在校园里设计了一个环形花坛，环上均匀分布着n nn个位置，编号为1 11到n nn，位置i ii与位置i + 1 i+1i+1相邻（位置n nn与位置1 11相邻）。每个位置可以种一棵花，花的种类用一个整数a i a_iai​表示，相同的整数代表同一种花。

瑞瑞想要选出一段连续的位置，使得这段位置里的花的种类数尽可能多。然而，由于环形花坛上的花形成环状，这段连续位置不能超过花坛半圈的长度，即所选区间的长度不能超过⌊ n / 2 ⌋ \lfloor n/2\rfloor⌊n/2⌋。

请你帮瑞瑞计算，在满足长度限制的条件下，一段连续位置中最多能包含多少种不同的花。

【输入】

第一行一个整数n nn，表示环形花坛的位置数量。
第二行n nn个整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1​,a2​,…,an​，表示每个位置上花的种类。

【输出】

输出一行一个整数，表示最多包含的不同花的种类数。

【输入样例】

6 1 2 3 1 2 3

【输出样例】

3

【核心思想】

1. 问题分析：给定环形数组a [ 1.. n ] a[1..n]a[1..n]（a i a_iai​表示花的种类），求长度不超过⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋的连续子数组中，不同元素个数的最大值。这是一个环形数组 + 滑动窗口问题，关键在于将环形结构通过"复制翻倍"转化为线性数组，再用双指针维护长度受限的窗口。

2. 算法选择：

   • 环形转线性（复制翻倍）：将数组复制为a [ 1..2 n ] a[1..2n]a[1..2n]，其中a [ i + n ] = a [ i ] a[i+n] = a[i]a[i+n]=a[i]，使得任意环形连续区间都对应线性数组上的一个连续子数组
   • 滑动窗口（双指针）：维护窗口[ i , j ] [i, j][i,j]，保证长度j − i + 1 ≤ ⌊ n / 2 ⌋ j - i + 1 \leq \lfloor n/2 \rfloorj−i+1≤⌊n/2⌋，用哈希/数组统计窗口内不同元素个数
   • 长度限制处理：当窗口长度超过限制时，收缩左端点i ii

3. 关键步骤：

   • 数组翻倍：读入a [ 1.. n ] a[1..n]a[1..n]，令a [ i + n ] = a [ i ] a[i+n] = a[i]a[i+n]=a[i]（i ii从1 11到n nn），得到长度2 n 2n2n的线性数组
   • 初始化：双指针i = 1 , j = 1 i = 1, j = 1i=1,j=1，计数数组cnt[]记录各元素出现次数，res记录当前窗口不同种类数
   • 滑动窗口（j jj从1 11遍历到2 n 2n2n）：
     • 长度检查：若j − i + 1 > ⌊ n / 2 ⌋ j - i + 1 > \lfloor n/2 \rfloorj−i+1>⌊n/2⌋，则右移i ii（cnt[a[i]]--，若变为0 00则res--）
     • 扩展右端点：将a [ j ] a[j]a[j]加入窗口（若cnt[a[j]] == 0则res++，然后cnt[a[j]]++）
     • 更新答案：ans = max(ans, res)
   • 输出a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，双指针每个位置最多被访问两次（入窗一次、出窗一次）
   • 空间复杂度：O ( n ) O(n)O(n)，翻倍数组2 n 2n2n和计数数组（离散化后种类数不超过n nn）

5. 双指针 + 环形处理的核心思想：

   • 环形转线性的经典技巧：复制数组实现O ( 1 ) O(1)O(1)的环形连续区间查询，避免取模运算和边界分裂讨论
   • 滑动窗口的长度约束：通过while循环严格维护窗口长度≤ ⌊ n / 2 ⌋ \leq \lfloor n/2 \rfloor≤⌊n/2⌋，保证满足题意
   • 计数数组维护不同元素个数：res只在元素首次入窗（cnt从0 00到1 11）和最后出窗（cnt从1 11到0 00）时变化，实现O ( 1 ) O(1)O(1)更新
   • 双指针的单调性：右指针j jj只增不减，左指针i ii只增不减，确保线性时间复杂度
   • 适用于环形数组的子数组统计问题，核心在于"复制翻倍消环"和"双指针维护受限窗口"

【算法标签】

#双指针

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 定义数组最大容量为100005intn,res,ans;// n为环形花坛位置数，res记录当前窗口内不同花的种类数，ans记录最大种类数inta[N*2];// 将环形数组复制一倍展开为线性数组，便于处理跨首尾的情况intcnt[N];// cnt[x]记录当前滑动窗口中花的种类x出现的次数map<int,int>mp;// mp未使用（原代码中用于离散化但直接用数组cnt替代了）intmain(){cin>>n;// 读入环形花坛的位置数量nfor(inti=1;i<=n;i++)// 读入每个位置的花的种类{cin>>a[i];// 读入第i个位置的花的种类a[i+n]=a[i];// 将数组复制一倍：a[n+1]=a[1], a[n+2]=a[2], ...}intlen=n/2;// 计算最大允许区间长度：不超过半圈，即floor(n/2)// 双指针滑动窗口：i为左端点，j为右端点for(inti=1,j=1;j<=2*n;j++)// j从1遍历到2n，枚举所有可能的右端点{// 当窗口长度超过len时，收缩左端点iwhile(j-i+1>len)// 如果当前窗口长度超过最大允许长度{--cnt[a[i]];// 左端点元素a[i]移出窗口，出现次数减1if(cnt[a[i]]==0)// 如果a[i]的出现次数变为0res--;// 窗口内不同种类数减1i++;// 左端点右移}// 将右端点元素a[j]加入窗口if(cnt[a[j]]==0)// 如果a[j]之前不在窗口中++res;// 窗口内不同种类数加1++cnt[a[j]];// a[j]的出现次数加1ans=max(ans,res);// 更新最大种类数}cout<<ans<<endl;// 输出满足长度限制的最大不同花种类数return0;}

【运行结果】

6 1 2 3 1 2 3 3