DeepSeek LeetCode 3605. 数组的最小稳定性因子 Python3实现

这道题的目标是，在最多修改 maxC 个元素后，最小化数组的“稳定性因子”（即最长“稳定子数组”的长度，其中稳定子数组的 GCD >= 2）。

核心思路是二分答案 + 贪心验证。

解题思路

1. 二分答案：我们需要找一个最小的 limit，使得我们可以通过最多 maxC 次修改，让所有稳定子数组的长度都不超过 limit。答案具有单调性，因此可以用二分搜索。
2. 贪心验证 (check(limit))：在验证一个 limit 是否可行时，关键是如何高效地判断。如果存在一个长度为 limit + 1 的稳定子数组，我们就必须在其中修改一个元素来“破坏”它。贪心策略是，遇到第一个需要破坏的稳定子数组时，直接修改其右端点的元素，因为这个位置能影响到后续最多的子数组。
3. 关键预处理 (left_min 数组)：为了快速判定任意以 i 为右端点的、GCD>=2的最长子数组的左边界，可以预处理出 left_min[i]。这个数组的含义是：以 i 为右端点的、满足 GCD>=2 的最长子数组的左端点索引。

Python3 实现

这里采用官方题解中的“优化（写法二）”，利用栈+滑动窗口的思想在 O(n) 时间内预处理 left_min，整体时间复杂度为 O(n log n)。

```python
import math
from typing import List
import bisect

class Solution:
def minStable(self, nums: List[int], maxC: int) -> int:
n = len(nums)
# 复制一份，因为下面的计算会修改数组内容
arr = nums[:]
left_min = [0] * n

# 1. 预处理 left_min 数组
# 采用栈+滑动窗口的方式，高效计算以每个位置为右端点的最长稳定子数组的左边界
left = 0
bottom = 0
right_gcd = 0
for 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:
# 重新构建栈，更新区间内的 GCD
for j in range(i - 1, left, -1):
arr[j] = math.gcd(arr[j], arr[j + 1])
bottom = i
right_gcd = 0
left += 1
left_min[i] = left

# 2. 定义二分查找的检查函数
def check(limit: int) -> bool:
# 判断是否能用最多 maxC 次修改，使稳定性因子不超过 limit
c = maxC
i = limit # 从第一个可能超过限制长度的子数组开始检查
while i < n:
# 如果以 i 为右端点的最长稳定子数组的长度大于 limit
if i - left_min[i] + 1 > limit:
if c == 0:
return False
c -= 1
# 贪心：修改当前右端点，跳过后续 limit 个位置
i += limit + 1
else:
i += 1
return True

# 3. 二分查找
# 上界可以优化为 n // (maxC + 1)，这是理论上限[citation:1]
ans = bisect.bisect_left(
range(n // (maxC + 1) + 1),
True,
key=lambda x: check(x)
)
return ans
```