javaclass 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];// 更新已有段落的 gcdfor (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 次修改使所有稳定子数组长度 upperprivate 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/(maxC1)] 之间。· 对于每个猜测值 mid我们检查能否通过最多 maxC 次修改让所有稳定子数组长度都不超过 mid。3. 贪心检查 (check 函数)· 从左到右扫描当发现以 i 结尾的稳定子数组长度 upper 时必须修改。· 最优策略是修改当前位置 i因为这样可以破坏所有包含 i 的稳定子数组。· 修改后直接跳跃 upper 1 个位置因为中间位置已经不可能再形成长度超过 upper 的稳定子数组了它们都包含了被修改的位置。