企业官网建设流程全解析

```java
class Solution {
public int minStable(int[] nums, int maxC) {
int n = nums.length;
// 如果 maxC 足够大，直接修改所有元素为 1，消除所有稳定子数组
int stableCnt = 0;
for (int v : nums) {
if (v >= 2) stableCnt++;
}
if (stableCnt <= maxC) return 0;

// leftMin[i] 表示以 i 为右端点，GCD >= 2 的最长子数组的左端点
// 若不存在，则 leftMin[i] = n (用 n 表示无效)
int[] leftMin = new int[n];
// segments 存储 [gcd值, 最左起始位置]，按 gcd 值去重
// 由于每个新元素最多产生 O(logV) 个不同 gcd 值，数组大小足够
int[][] segments = new int[35][2];
int size = 0;

for (int i = 0; i < n; i++) {
int x = nums[i];
// 更新已有段落的 gcd
for (int j = 0; j < size; j++) {
segments[j][0] = gcd(segments[j][0], x);
}
// 添加当前元素自身作为新段落 [x, i]
segments[size][0] = x;
segments[size][1] = i;
size++;

// 去重：合并 gcd 值相同的相邻段落，保留最左起始位置
int write = 0;
for (int j = 0; j < size; j++) {
if (write == 0 || segments[j][0] != segments[write - 1][0]) {
segments[write][0] = segments[j][0];
segments[write][1] = segments[j][1];
write++;
}
}
size = write;

// 从左往右找第一个 gcd >= 2 的段落，它对应的左端点就是 leftMin[i]
// 因为 segments 按从左到右顺序存储，第一个满足条件的即为最左起始位置
leftMin[i] = n; // 默认不存在
for (int j = 0; j < size; j++) {
if (segments[j][0] >= 2) {
leftMin[i] = segments[j][1];
break;
}
}
}

// 二分答案：最长稳定子数组长度的上界
// 优化上界：最多 maxC 次修改最多将数组分成 maxC + 1 段
int left = 0, right = n / (maxC + 1) + 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (check(leftMin, maxC, mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
}

// 检查：能否通过最多 maxC 次修改，使所有稳定子数组长度 <= upper
private boolean check(int[] leftMin, int maxC, int upper) {
int n = leftMin.length;
int used = 0;
int i = upper;
while (i < n) {
// 如果 leftMin[i] == n，说明不存在以 i 为右端点的稳定子数组
if (leftMin[i] < n) {
int len = i - leftMin[i] + 1;
if (len > upper) {
used++;
if (used > maxC) return false;
// 修改位置 i，跳过 upper 个位置
// 因为任何包含 i 的长度 <= upper 的子数组都会被破坏
i += upper + 1;
continue;
}
}
i++;
}
return true;
}

private int gcd(int a, int b) {
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
}
```

核心思路

这个问题可以用二分答案 + 贪心来解决。

1. 预处理 leftMin 数组
我们需要快速知道：以每个位置 i 为右端点，GCD >= 2 的最长稳定子数组的左端点在哪里。这里使用了LogTrick技巧，利用GCD值种类很少（不超过logV）的性质来高效计算。

2. 二分答案

· 答案范围在 [0, n/(maxC+1)] 之间。
· 对于每个猜测值 mid，我们检查能否通过最多 maxC 次修改，让所有稳定子数组长度都不超过 mid。

3. 贪心检查 (check 函数)

· 从左到右扫描，当发现以 i 结尾的稳定子数组长度 > upper 时，必须修改。
· 最优策略是修改当前位置 i，因为这样可以破坏所有包含 i 的稳定子数组。
· 修改后，直接跳跃 upper + 1 个位置，因为中间位置已经不可能再形成长度超过 upper 的稳定子数组了（它们都包含了被修改的位置）。