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

这个问题的核心是二分答案 + 贪心验证，其中预处理所有长度为 mid+1 的稳定子数组是关键。

这里提供一个结合了线段树进行区间 GCD 查询和贪心区间覆盖的 Rust 实现，思路清晰且易于理解。

```rust
use std::cmp::max;

impl Solution {
pub fn min_stable(nums: Vec<i32>, max_c: i32) -> i32 {
let n = nums.len();
if n == 0 {
return 0;
}

// 构建线段树用于快速查询任意区间的 GCD
let mut size = 1;
while size < n {
size <<= 1;
}
let mut seg = vec![0; size * 2];
for i in 0..n {
seg[size + i] = nums[i];
}
for i in (1..size).rev() {
seg[i] = Self::gcd(seg[i * 2], seg[i * 2 + 1]);
}

// 闭包：查询区间 [l, r] 的 GCD
let range_gcd = |l: usize, r: usize| -> i32 {
let mut l = l + size;
let mut r = r + size;
let mut res_left = 0;
let mut res_right = 0;
while l <= r {
if l % 2 == 1 {
res_left = Self::gcd(res_left, seg[l]);
l += 1;
}
if r % 2 == 0 {
res_right = Self::gcd(seg[r], res_right);
r -= 1;
}
l >>= 1;
r >>= 1;
}
Self::gcd(res_left, res_right)
};

// 验证函数：检查稳定性因子是否 <= limit
let feasible = |limit: usize| -> bool {
let mut used = 0;
let mut last_chosen = -1; // 上一个修改点的位置

// 只需检查所有长度为 limit + 1 的窗口
for start in 0..(n - limit) {
let end = start + limit;
// 如果窗口 GCD >= 2，则这是一个必须被“破坏”的稳定子数组
if range_gcd(start, end) >= 2 {
// 如果上一个修改点不在当前窗口内，则必须在此窗口内进行一次修改
if last_chosen < start as isize {
used += 1;
last_chosen = end as isize; // 贪心地选择窗口右端点
if used > max_c {
return false;
}
}
}
}
true
};

// 二分查找最小可行的稳定性因子
let mut left = 0;
let mut right = n;
while left < right {
let mid = (left + right) / 2;
if feasible(mid) {
right = mid;
} else {
left = mid + 1;
}
}
left as i32
}

// 辅助 gcd 函数
fn gcd(a: i32, b: i32) -> i32 {
if b == 0 { a } else { Self::gcd(b, a % b) }
}
}
```

核心思路说明

1. 问题转化：判断能否通过最多 maxC 次修改，使数组的“稳定性因子”不超过 L。这等价于判断所有长度为 L+1 的稳定子数组（GCD >= 2）能否被最多 maxC 个点“击中”。
2. 贪心验证 (Greedy Check)：对于给定的 L，从左到右扫描所有长度为 L+1 的窗口。如果遇到一个稳定窗口，就在其右端点处进行修改（相当于放置一个“断点”）。这是处理区间覆盖问题的最优贪心策略：要覆盖一个区间，点在右端点能最大化覆盖后续区间的可能性。统计所需的修改次数，若不超过 maxC，则 L 可行。
3. 区间 GCD 查询：为了快速判断一个窗口是否稳定，需要使用高效的数据结构。这里选择线段树，可以在 O(log n) 时间内查询任意区间的 GCD，预处理复杂度 O(n)。另一种更优的预处理方法是 LogTrick，可以在 O(n log U) 时间内算出所有位置的关键信息，并用于 O(n) 的验证。
4. 二分答案：可行性关于 L 是单调的（L 越大越容易实现），因此可以对答案 [0, n] 进行二分，找到最小的可行 L。