• 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。