🔥刷题之探索最优解 WIP#

1// 方法一：
2function rope(arr, k) {
3  let res = 1
4  for (let i = 0; i < arr.length; i++) {
5    let near = Dichotomous(arr, i, arr[i] - k) // 求数组中大于等于arr[i]-k的最小数
6    res = Math.max(res, i - near + 1)
7  }
8  return res
9}
10
11function Dichotomous(arr, r, value) {
12  let index = r
13  let l = 0
14  while (l < r) {
15    let mid = Math.floor((l + r) / 2)
16    if (arr[mid] >= value) {
17      r = mid - 1
18      index = mid
19    } else {
20      l = mid + 1
21    }
22  }
23  return index
24}
25// 方法二：
26function rope(arr, k) {
27  let l = 0,
28    r = 0,
29    n = arr.length
30  max = 0
31  while (l < n) {
32    while (r < n && arr[r] - arr[l] <= k) r++
33    max = Math.max(max, r - l++)
34  }
35  return max
36}