2025-12-16：数组的最小稳定性因子。用go语言，给定一个整数数组 nums 和一个整数 maxC。把满足以下条件的连续区间称为“稳定子数组”：区间内所有数的最大公约数（GCD）至少为 2。
定义数组的“稳定性因子”为其最长稳定子数组的长度。你可以最多对数组中的 maxC 个位置改成任意整数。问题是：在不超过 maxC 次修改后，能够把稳定性因子降到多小？返回这个最小可能的稳定性因子；如果最终不存在任何稳定子数组，则返回 0。
补充说明：
子数组指数组的连续片段。
数组的最大公约数指能同时整除所有元素的最大整数。
长度为 1 的子数组若其唯一元素 ≥ 2，也视为稳定子数组。
1 <= n == nums.length <= 100000。
1 <= nums[i] <= 1000000000。
0 <= maxC <= n。
输入：nums = [3,5,10], maxC = 1。
输出：1。
解释：
稳定的子数组 [5, 10] 的 HCF = 5，其稳定性因子为 2。
由于 maxC = 1，一个最优策略是将 nums[1] 改为 7，得到 nums = [3, 7, 10]。
现在，没有长度大于 1 的子数组的 HCF >= 2。因此，最小可能稳定性因子是 1。
题目来自力扣3605。
🔍 算法步骤详解
初始化与预处理
- 函数首先获取数组长度
n，并初始化一个与nums等长的切片leftMin。这个切片用于记录一个关键信息：对于每个位置i，leftMin[i]表示以i为区间右端点时，能够使得区间内所有元素的最大公约数（GCD）大于等于2的、最靠左的起点位置。 - 变量
left和bottom初始化为0，它们共同维护一个滑动窗口或处理区间。rightGcd初始化为0（因为任何数与0的GCD是其本身）。
- 函数首先获取数组长度
计算 leftMin 数组
- 这是算法的核心步骤。它通过一次遍历（下标
i从0到n-1）来计算leftMin数组。 - 更新GCD：对于当前元素
nums[i]，代码通过rightGcd = gcd(rightGcd, nums[i])来累积计算从某个起点到i的整个区间的GCD。 - 收缩左边界：使用一个内层循环（
for left <= i && gcd(nums[left], rightGcd) == 1）来调整左边界left。这个条件的目的是检查当前窗口[left, i]的GCD是否因为包含了nums[left]而变为1（即不满足稳定子数组条件）。如果变为1，就需要向右移动left指针，直到窗口内的GCD再次大于等于2，或者窗口为空。 - 记录左边界：将最终确定的左边界
left记录到leftMin[i]中。 - 栈式重建（关键优化）：当需要移动
left指针，并且bottom（可以理解为上一次重建的起始点）小于或等于当前的left时，会触发一个重建操作。这个操作从i-1到left+1逆序地重新计算区间GCD，这类似于维护一个隐式的栈结构，用于高效地更新GCD信息，避免每次都从头计算。完成后，bottom被更新为i，rightGcd重置为0。
- 这是算法的核心步骤。它通过一次遍历（下标
二分查找最小稳定性因子
- 在得到
leftMin数组后，算法使用二分搜索来确定最小的稳定性因子（即最长稳定子数组的长度上限upper）。 - 搜索范围：二分查找的下界是0，上界可以设为
n/(maxC+1)，这是一个合理的估计，因为修改maxC个点最多能将数组分成maxC+1段。 - 检查函数：对于每一个候选的
upper值，函数模拟修改操作，检查是否能在最多maxC次修改后，使得数组中所有稳定子数组的长度都不超过upper。 - 贪心模拟：检查过程采用贪心策略。从左到右遍历数组，当遇到一个稳定子数组的长度超过
upper时（即i - leftMin[i] + 1 > upper），就在这个子数组的末尾之后进行一次“修改”（实际上是通过将索引i跳转upper + 1位来模拟），并消耗一次修改次数。如果修改次数在遍历完数组前用完，则说明当前upper值太小，需要增大；否则，说明upper值可行，可以尝试更小的值。
- 在得到
返回结果
- 二分查找结束后，找到的最小满足条件的
upper值就是题目要求的最小可能稳定性因子，将其返回。
- 二分查找结束后，找到的最小满足条件的
⏱ 复杂度分析
时间复杂度
- 计算
leftMin数组：主循环遍历每个元素一次。虽然内部有循环和重建操作，但每个元素最多被加入和移出“栈”一次，GCD计算可以看作是常数时间（因为整数大小有限，GCD操作很快）。因此，这部分的时间复杂度可以看作是O(n)。 - 二分查找与检查：二分查找的迭代次数是O(log n)。每次检查需要遍历整个数组，是O(n)。所以这部分的总时间复杂度是O(n log n)。
- 综合：整个算法的总时间复杂度为 O(n log n)。
空间复杂度
- 算法主要使用了
leftMin数组，其大小为O(n)。 - 其他变量如
left,bottom,rightGcd等占用常数空间。 - 在计算GCD的递归或栈模拟过程中，没有使用与输入规模成比例的额外数据结构。
- 因此，算法的总额外空间复杂度为 O(n)。
Go完整代码如下：
packagemainimport("fmt""sort")funcminStable(nums[]int,maxCint)int{n:=len(nums)leftMin:=make([]int,n)varleft,bottom,rightGcdintfori,x:=rangenums{rightGcd=gcd(rightGcd,x)forleft<=i&&gcd(nums[left],rightGcd)==1{ifbottom<=left{// 重新构建一个栈// 由于 left 即将移出窗口，只需计算到 left+1forj:=i-1;j>left;j--{nums[j]=gcd(nums[j],nums[j+1])}bottom=i rightGcd=0}left++}leftMin[i]=left}ans:=sort.Search(n/(maxC+1),func(upperint)bool{c:=maxC i:=upperfori<n{ifi-leftMin[i]+1>upper{ifc==0{returnfalse}c--i+=upper+1}else{i++}}returntrue})returnans}funcgcd(a,bint)int{fora!=0{a,b=b%a,a}returnb}funcmain(){nums:=[]int{3,5,10}maxC:=1result:=minStable(nums,maxC)fmt.Println(result)}Python完整代码如下：
# -*-coding:utf-8-*-importmathfromtypingimportListimportbisectdefminStable(nums:List[int],maxC:int)->int:n=len(nums)leftMin=[0]*n left=0bottom=0rightGcd=0foriinrange(n):x=nums[i]rightGcd=math.gcd(rightGcd,x)whileleft<=iandmath.gcd(nums[left],rightGcd)==1:ifbottom<=left:# 重新构建一个栈# 由于 left 即将移出窗口，只需计算到 left+1forjinrange(i-1,left,-1):nums[j]=math.gcd(nums[j],nums[j+1])bottom=i rightGcd=0left+=1leftMin[i]=left# 二分查找defcheck(upper:int)->bool:c=maxC i=upperwhilei<n:ifi-leftMin[i]+1>upper:ifc==0:returnFalsec-=1i+=upper+1else:i+=1returnTrue# 使用二分查找找到最小满足条件的值low,high=0,n//(maxC+1)+1whilelow<high:mid=(low+high)//2ifcheck(mid):high=midelse:low=mid+1returnlow# 另一种更简洁的二分查找实现方式defminStable_alternative(nums:List[int],maxC:int)->int:n=len(nums)leftMin=[0]*n left=0bottom=0rightGcd=0foriinrange(n):x=nums[i]rightGcd=math.gcd(rightGcd,x)whileleft<=iandmath.gcd(nums[left],rightGcd)==1:ifbottom<=left:# 重新构建一个栈forjinrange(i-1,left,-1):nums[j]=math.gcd(nums[j],nums[j+1])bottom=i rightGcd=0left+=1leftMin[i]=left# 使用 Python 的 bisect 风格二分查找ans=bisect.bisect_left(range(n//(maxC+1)+1),True,key=lambdaupper:check(upper))defcheck(upper:int)->bool:c=maxC i=upperwhilei<n:ifi-leftMin[i]+1>upper:ifc==0:returnFalsec-=1i+=upper+1else:i+=1returnTruereturnans# 测试代码if__name__=="__main__":nums=[3,5,10]maxC=1result=minStable(nums,maxC)print(f"minStable result:{result}")# 测试更多用例test_cases=[([3,5,10],1),([2,3,4,5],2),([1,2,3,4,5],1),([6,10,15],0),]fornums,maxCintest_cases:result=minStable(nums.copy(),maxC)print(f"nums={nums}, maxC={maxC}-> result={result}")C++完整代码如下：
#include<iostream>#include<vector>#include<algorithm>#include<functional>#include<numeric>usingnamespacestd;intgcd(inta,intb){while(a!=0){inttemp=a;a=b%a;b=temp;}returnb;}intminStable(vector<int>&nums,intmaxC){intn=nums.size();vector<int>leftMin(n,0);intleft=0,bottom=0,rightGcd=0;for(inti=0;i<n;i++){intx=nums[i];rightGcd=gcd(rightGcd,x);while(left<=i&&gcd(nums[left],rightGcd)==1){if(bottom<=left){// 重新构建一个栈// 由于 left 即将移出窗口，只需计算到 left+1for(intj=i-1;j>left;j--){nums[j]=gcd(nums[j],nums[j+1]);}bottom=i;rightGcd=0;}left++;}leftMin[i]=left;}// 二分查找autocheck=[&](intupper)->bool{intc=maxC;inti=upper;while(i<n){if(i-leftMin[i]+1>upper){if(c==0){returnfalse;}c--;i+=upper+1;}else{i++;}}returntrue;};intlow=0,high=n/(maxC+1)+1;while(low<high){intmid=low+(high-low)/2;if(check(mid)){high=mid;}else{low=mid+1;}}returnlow;}// 使用C++标准库的binary_search风格intminStable2(vector<int>&nums,intmaxC){intn=nums.size();vector<int>leftMin(n,0);intleft=0,bottom=0,rightGcd=0;for(inti=0;i<n;i++){intx=nums[i];rightGcd=gcd(rightGcd,x);while(left<=i&&gcd(nums[left],rightGcd)==1){if(bottom<=left){// 重新构建一个栈for(intj=i-1;j>left;j--){nums[j]=gcd(nums[j],nums[j+1]);}bottom=i;rightGcd=0;}left++;}leftMin[i]=left;}// 使用lower_bound风格的二分查找vector<int>range(n/(maxC+1)+1);for(inti=0;i<range.size();i++){range[i]=i;}autoit=lower_bound(range.begin(),range.end(),true,[&](intupper,bool){intc=maxC;inti=upper;while(i<n){if(i-leftMin[i]+1>upper){if(c==0){returntrue;// 返回true表示upper不够大}c--;i+=upper+1;}else{i++;}}returnfalse;// 返回false表示upper足够大});return(it!=range.end())?*it:n;}intmain(){vector<int>nums={3,5,10};intmaxC=1;intresult=minStable(nums,maxC);cout<<"minStable result: "<<result<<endl;// 测试更多用例vector<pair<vector<int>,int>>testCases={{{3,5,10},1},{{2,3,4,5},2},{{1,2,3,4,5},1},{{6,10,15},0},};for(auto&testCase:testCases){vector<int>numsCopy=testCase.first;intmaxC=testCase.second;intresult=minStable(numsCopy,maxC);cout<<"nums=[";for(size_t i=0;i<testCase.first.size();i++){cout<<testCase.first[i];if(i<testCase.first.size()-1)cout<<", ";}cout<<"], maxC="<<maxC<<" -> result="<<result<<endl;}return0;}
