3605. 数组的最小稳定性因子

Hard

题目描述

给你一个整数数组 nums 和一个整数 maxC。

如果一个子数组的所有元素的最大公约数（HCF）大于或等于 2，则称该子数组为稳定的。

数组的稳定性因子定义为其最长稳定子数组的长度。

你最多可以将数组中的 maxC 个元素修改为任意整数。

返回经过最多 maxC 次修改后，数组的最小可能稳定性因子。如果没有稳定子数组剩余，则返回 0。

注意：

数组的最大公约数（HCF）是能整除数组所有元素的最大整数。
长度为 1 的子数组如果其唯一元素大于或等于 2，则是稳定的，因为 HCF([x]) = x。

示例 1：

输入：nums = [3,5,10], maxC = 1
输出：1
解释：
稳定子数组 [5, 10] 的 HCF = 5，稳定性因子为 2。
由于 maxC = 1，一种最优策略是将 nums[1] 改为 7，得到 nums = [3, 7, 10]。
现在，长度大于 1 的子数组都没有 HCF >= 2。因此，最小可能的稳定性因子是 1。

示例 2：

输入：nums = [2,6,8], maxC = 2
输出：1
解释：
子数组 [2, 6, 8] 的 HCF = 2，稳定性因子为 3。
由于 maxC = 2，一种最优策略是将 nums[1] 改为 3，nums[2] 改为 5，得到 nums = [2, 3, 5]。
现在，长度大于 1 的子数组都没有 HCF >= 2。因此，最小可能的稳定性因子是 1。

示例 3：

输入：nums = [2,4,9,6], maxC = 1
输出：2
解释：
稳定子数组有：
- [2, 4] 的 HCF = 2，稳定性因子为 2
- [9, 6] 的 HCF = 3，稳定性因子为 2
由于 maxC = 1，稳定性因子 2 无法减少，因为有两个独立的稳定子数组。因此，最小可能的稳定性因子是 2。

约束条件：

1 <= n == nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= maxC <= n

解题思路

这是一道结合了数学、二分搜索和贪心策略的复杂题目。

核心思路：

问题转化：我们需要找到最小的稳定性因子，即通过修改元素来最小化最长稳定子数组的长度。
二分搜索：对答案进行二分搜索。对于每个候选答案 k，检查是否可能使得所有长度超过 k 的子数组都不稳定（GCD < 2）。
区间GCD查询：对于长度为 k+1 的滑动窗口，我们需要快速计算其GCD。可以使用稀疏表（Sparse Table）或线段树来实现O(1)或O(log n)的区间GCD查询。
贪心策略：当发现一个长度为 k+1 的窗口GCD ≥ 2时，我们需要修改其中一个元素来破坏这个稳定性。贪心地选择修改窗口的最后一个元素，这样可以最大化对后续窗口的影响。
实现细节：
- 使用二分搜索确定最小可能的稳定性因子
- 对于每个候选值，扫描所有长度为 k+1 的窗口
- 统计需要修改的元素数量，如果不超过 maxC 则该候选值可行

算法流程：

二分搜索答案范围 [0, n]
对于每个候选答案 mid，检查是否可以通过最多 maxC 次修改使得最长稳定子数组长度不超过 mid
使用贪心策略计算所需的最少修改次数

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    bool canAchieve(vector<int>& nums, int maxLen, int maxC) {
        int n = nums.size();
        if (maxLen >= n) return true;
        
        int changes = 0;
        int i = 0;
        
        while (i <= n - maxLen - 1) {
            int g = nums[i];
            for (int j = i + 1; j <= i + maxLen; j++) {
                g = gcd(g, nums[j]);
                if (g == 1) break;
            }
            
            if (g > 1) {
                changes++;
                if (changes > maxC) return false;
                i += maxLen + 1;  // Skip the entire window
            } else {
                i++;
            }
        }
        
        return true;
    }
    
    int minStable(vector<int>& nums, int maxC) {
        int n = nums.size();
        int left = 0, right = n;
        int result = n;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canAchieve(nums, mid, maxC)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def minStable(self, nums: List[int], maxC: int) -> int:
        import math
        
        def can_achieve(max_len):
            if max_len >= len(nums):
                return True
            
            changes = 0
            i = 0
            
            while i <= len(nums) - max_len - 1:
                g = nums[i]
                for j in range(i + 1, i + max_len + 1):
                    g = math.gcd(g, nums[j])
                    if g == 1:
                        break
                
                if g > 1:
                    changes += 1
                    if changes > maxC:
                        return False
                    i += max_len + 1  # Skip the entire window
                else:
                    i += 1
            
            return True
        
        left, right = 0, len(nums)
        result = len(nums)
        
        while left <= right:
            mid = (left + right) // 2
            if can_achieve(mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    private int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private bool CanAchieve(int[] nums, int maxLen, int maxC) {
        int n = nums.Length;
        if (maxLen >= n) return true;
        
        int changes = 0;
        int i = 0;
        
        while (i <= n - maxLen - 1) {
            int g = nums[i];
            for (int j = i + 1; j <= i + maxLen; j++) {
                g = Gcd(g, nums[j]);
                if (g == 1) break;
            }
            
            if (g > 1) {
                changes++;
                if (changes > maxC) return false;
                i += maxLen + 1;  // Skip the entire window
            } else {
                i++;
            }
        }
        
        return true;
    }
    
    public int MinStable(int[] nums, int maxC) {
        int n = nums.Length;
        int left = 0, right = n;
        int result = n;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (CanAchieve(nums, mid, maxC)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

var minStable = function(nums, maxC) {
    const n = nums.length;
    
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    function getGCD(arr) {
        if (arr.length === 0) return 0;
        let result = arr[0];
        for (let i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);
            if (result === 1) return 1;
        }
        return result;
    }
    
    function canAchieve(targetStability) {
        let changes = 0;
        let i = 0;
        
        while (i < n) {
            let maxLen = 0;
            
            for (let j = i; j < n; j++) {
                let subarray = nums.slice(i, j + 1);
                if (getGCD(subarray) >= 2) {
                    maxLen = j - i + 1;
                }
            }
            
            if (maxLen >= targetStability) {
                if (maxLen > targetStability) {
                    changes++;
                    if (changes > maxC) return false;
                }
                i += maxLen;
            } else {
                if (nums[i] >= 2) {
                    i++;
                } else {
                    changes++;
                    if (changes > maxC) return false;
                    i++;
                }
            }
        }
        
        return true;
    }
    
    let left = 1, right = n;
    let result = n;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canAchieve(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
整体复杂度	O(n² log n log max(nums))	O(1)
二分搜索	O(log n)	O(1)
单次检查	O(n² log max(nums))	O(1)

其中 n 是数组长度，max(nums) 是数组中的最大值。GCD计算的复杂度为 O(log max(nums))。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析