绳子盖住的最多点

一、题目描述：

给定一个有序数组arr 从左到右依次表示X轴上从左往右点的位置，给定一个正整数k， 返回如果有一根长度为k的绳子，最多能盖住几个点，绳子的边缘点碰到X轴上的点，也算盖住。

示例：

示例 1：输入：arr = [1, 5, 13, 14, 15, 32, 43], k = 2

输出：3

示例 2：输入：arr = [1, 5, 13, 14, 15, 32, 43], k = 5

输出：3

二、思路分析：

绳子的长度为整数，所以绳头和绳尾需要盖在点。

方法一：

遍历时，将数组中的每一个数都看作绳尾盖住的点，求绳头能盖住的最大点。 例子： arr = [1,3,7,9,11,13,14,15], k = 5

当结尾为5时，绳子可以往前到0位置，覆盖2个点；

....

由此可以看出， 当结尾为arr[i]时，绳子可以达到arr[i]-k的位置。所以我们只需要求出arr中大于等于arr[i]-k的最小值，通过当前下标减去最小值的下标再加一就等于绳子覆盖的点数。再使用一个变量保存覆盖点数的最大值即可。

当i = 4时，arr[i] = 11, a[i] - k = 6。只需要在数组中查找的大于6的最小值，获取其下标，即最小值下标为2。覆盖点数为：i - 2 + 1 = 3。

其中最核心的就是求大于某个值的最小下标，我们可以使用二分来实现。

方法二：

看到数组存在单调性，就可以想到使用窗口法解决此问题。定义两个左右指针l、r，左右不停往右不回头。在r往右时，需要注意覆盖的头和尾之间长度是否小于等于绳子长度，即arr[r] - arr[l] <= k。

三、AC 代码：

// 方法一：
function rope(arr, k) {
  let res = 1
  for (let i = 0; i < arr.length; i++) {
    let near = Dichotomous(arr, i, arr[i] - k) // 求数组中大于等于arr[i]-k的最小数
    res = Math.max(res, i - near + 1)
  }
  return res
}
function Dichotomous(arr, r, value) {
  let index = r
  let l = 0
  while (l < r) {
    let mid = Math.floor((l + r) / 2)
    if (arr[mid] >= value) {
      r = mid - 1
      index = mid
    } else {
      l = mid + 1
    }
  }
  return index
}
// 方法二：
function rope(arr, k) {
  let l = 0,
    r = 0,
    n = arr.length
  max = 0
  while (l < n) {
    while (r < n && arr[r] - arr[l] <= k) r++
    max = Math.max(max, r - l++)
  }
  return max
}

四、总结：

在解决问题的基础上，再进行优化。方法一使用二分复杂度为O(nlogn)，使用窗口法就可以将复杂度将为O(n)。

作者：ClyingDeng

链接：https://juejin.cn/post/6951203359378374687

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。