[leetcode 3605][Go][二分答案]能二分的不只有数组

题目链接

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

解题思路

这道题说难不难，只是追求通过所有实例的话只要根据题目中最小化最大值想到二分答案就能做到$O(n \log n \log V)(V=max(nums))$的时间复杂度

单次计算

这里声明一个子函数func sub(nums []int, maxC int, length int) bool用于计算maxC次操作内能否使最长稳定子数组的长度小于等于length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func gcd(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func sub(nums []int, maxC int, length int) bool {
	var leng = len(nums)
	var arr = slices.Clone(nums)
	var g = 1
    //l和r用于表示以r结尾的最长稳定子数组
    //l,r为左开右闭区间，根据个人喜好决定
	for l, r := -1, 0; r < leng && maxC >= 0; r++ {
		g = gcd(max(arr[r], g), min(arr[r], g))
        //当发现(l,r]区间不再稳定则重新计算l坐标
		if g < 2 {
			l = r
			g = arr[r]
			for ; l >= 0; l-- {
				t := gcd(max(arr[l], g), min(arr[l], g))
                //当发现[l, r]上存在至少两个数互质时立即跳出循环
                //确保(l,r]为稳定子数组
				if t >= 2 {
					g = t
				} else {
					break
				}
			}
		}
		if r-l > length {
			arr[r] = 1
			g = 1
			l = r
			maxC--
		}
	}
	return maxC >= 0
}

这里触发内循环(重新计算l坐标)的条件是(l, r]最大公因数为1(即至少存在两个互质的元素)而单次内循环的时间复杂度达到$O(n)$的条件是[0, r]上没有元素互质或者互质的元素下标靠近0，同时达到上述条件显然是不可能的，所以sub的时间复杂度为$O(n\log V)(V=max(nums))$

答案二分

接下来只要用二分法确定sub返回true的最小长度就行了

1
2
3
4
5
6
7
8
func minStable(nums []int, maxC int) int {
    //最小可能的稳定子数组长度为0，最大可能长度为len(nums)
    //所以直接定义边界[0,len(nums)+1)并执行二分查找就行
	var ret = sort.Search(len(nums)+1, func(i int) bool {
		return sub(nums, maxC, i)
	})
	return ret
}