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

这个问题的核心是二分答案 贪心验证其中预处理所有长度为 mid1 的稳定子数组是关键。这里提供一个结合了线段树进行区间 GCD 查询和贪心区间覆盖的 Rust 实现思路清晰且易于理解。rustuse std::cmp::max;impl Solution {pub fn min_stable(nums: Veci32, max_c: i32) - i32 {let n nums.len();if n 0 {return 0;}// 构建线段树用于快速查询任意区间的 GCDlet 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] 的 GCDlet 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)};// 验证函数检查稳定性因子是否 limitlet 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。这等价于判断所有长度为 L1 的稳定子数组GCD 2能否被最多 maxC 个点“击中”。2. 贪心验证 (Greedy Check)对于给定的 L从左到右扫描所有长度为 L1 的窗口。如果遇到一个稳定窗口就在其右端点处进行修改相当于放置一个“断点”。这是处理区间覆盖问题的最优贪心策略要覆盖一个区间点在右端点能最大化覆盖后续区间的可能性。统计所需的修改次数若不超过 maxC则 L 可行。3. 区间 GCD 查询为了快速判断一个窗口是否稳定需要使用高效的数据结构。这里选择线段树可以在 O(log n) 时间内查询任意区间的 GCD预处理复杂度 O(n)。另一种更优的预处理方法是 LogTrick可以在 O(n log U) 时间内算出所有位置的关键信息并用于 O(n) 的验证。4. 二分答案可行性关于 L 是单调的L 越大越容易实现因此可以对答案 [0, n] 进行二分找到最小的可行 L。