这道题的目标是在最多修改 maxC 个元素后最小化数组的“稳定性因子”即最长“稳定子数组”的长度其中稳定子数组的 GCD 2。核心思路是二分答案 贪心验证。解题思路1. 二分答案我们需要找一个最小的 limit使得我们可以通过最多 maxC 次修改让所有稳定子数组的长度都不超过 limit。答案具有单调性因此可以用二分搜索。2. 贪心验证 (check(limit))在验证一个 limit 是否可行时关键是如何高效地判断。如果存在一个长度为 limit 1 的稳定子数组我们就必须在其中修改一个元素来“破坏”它。贪心策略是遇到第一个需要破坏的稳定子数组时直接修改其右端点的元素因为这个位置能影响到后续最多的子数组。3. 关键预处理 (left_min 数组)为了快速判定任意以 i 为右端点的、GCD2的最长子数组的左边界可以预处理出 left_min[i]。这个数组的含义是以 i 为右端点的、满足 GCD2 的最长子数组的左端点索引。Python3 实现这里采用官方题解中的“优化写法二”利用栈滑动窗口的思想在 O(n) 时间内预处理 left_min整体时间复杂度为 O(n log n)。pythonimport mathfrom typing import Listimport bisectclass Solution:def minStable(self, nums: List[int], maxC: int) - int:n len(nums)# 复制一份因为下面的计算会修改数组内容arr nums[:]left_min [0] * n# 1. 预处理 left_min 数组# 采用栈滑动窗口的方式高效计算以每个位置为右端点的最长稳定子数组的左边界left 0bottom 0right_gcd 0for i, x in enumerate(arr):right_gcd math.gcd(right_gcd, x)while left i and math.gcd(arr[left], right_gcd) 1:# 如果当前窗口的 GCD 变为 1则需要移动左边界if bottom left:# 重新构建栈更新区间内的 GCDfor j in range(i - 1, left, -1):arr[j] math.gcd(arr[j], arr[j 1])bottom iright_gcd 0left 1left_min[i] left# 2. 定义二分查找的检查函数def check(limit: int) - bool:# 判断是否能用最多 maxC 次修改使稳定性因子不超过 limitc maxCi limit # 从第一个可能超过限制长度的子数组开始检查while i n:# 如果以 i 为右端点的最长稳定子数组的长度大于 limitif i - left_min[i] 1 limit:if c 0:return Falsec - 1# 贪心修改当前右端点跳过后续 limit 个位置i limit 1else:i 1return True# 3. 二分查找# 上界可以优化为 n // (maxC 1)这是理论上限[citation:1]ans bisect.bisect_left(range(n // (maxC 1) 1),True,keylambda x: check(x))return ans