• Leetcode 3605. Minimum Stability Factor of Array
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3605. Minimum Stability Factor of Array

1. 解题思路

这一题的核心思路是二分法，本质上就是我们给定一个常数$k$，然后考察是否存在一个构造使得能够在$maxC$的操作内使得数组当中任意长度不超过$k$的子串的HCF均为$1$。然后我们二分检索最小能够满足条件的$k$即可。

于是，剩下的问题就是给定一个常数$k$之后，如何判断其是否存在对应的构造即可，这个我们只需要考察所有长度为$k+1$的子串，如果其HCF为1，那么对应的数组满足条件，我们考察下一个位置即可，如果其不为1，那么我们将第$k+1$个元素变为$1$，此时，前面所有的子串均可满足条件，我们考察第$k+2$个元素开始的所有子串即可。

但这里的难点就在于说需要快速地求得任意范围$[i,j]$的最大公约数，这里我自己没能搞定，看了一下答案之后发现可以使用分段树进行处理，而分段树本身是个经典算法，这里就不赘述了，我自己也有一篇水文《经典算法：Segment Tree》作为备忘，有兴趣的读者自己去网上查一下了解一下就行了。

2. 代码实现

给出python代码实现如下：

class SegmentTree:def __init__(self, arr):self.length = len(arr)self.tree = self.build(arr)def feature_func(self, *args):args = list(args)def fn(arr):n = len(arr)if n == 1:return arr[0]elif n == 2:return gcd(arr[0], arr[1])else:return gcd(fn(arr[:n//2]), fn(arr[n//2:]))return fn(args)def build(self, arr):n = len(arr)tree = [0 for _ in range(2*n)]for i in range(n):tree[i+n] = arr[i]for i in range(n-1, 0, -1):tree[i] = self.feature_func(tree[i<<1], tree[(i<<1) | 1])return treedef update(self, idx, val):idx = idx + self.lengthself.tree[idx] = valwhile idx > 1:self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx = idx>>1returndef query(self, lb, rb):lb += self.length rb += self.lengthnodes = []while lb < rb:if lb & 1 == 1:nodes.append(self.tree[lb])lb += 1if rb & 1 == 0:nodes.append(self.tree[rb])rb -= 1lb = lb >> 1rb = rb >> 1if lb == rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)class Solution:def minStable(self, nums: List[int], maxC: int) -> int:n = len(nums)if n - Counter(nums)[1] <= maxC:return 0 segment_tree = SegmentTree(nums)def is_possible(k):idx, cnt = 0, 0while idx + k < n:if segment_tree.query(idx, idx+k) <= 1:idx += 1else:cnt += 1idx += k+1if cnt > maxC:return Falsereturn Truei, j = 1, nif is_possible(1):return 1while j-i>1:k = (i+j)//2if is_possible(k):j = kelse:i = kreturn j

提交代码评测得到：耗时5745ms，占用内存34.37MB。