I. Title Description:

Given an ordered array arr representing the positions of points on the X-axis from left to right, and given a positive integer k, return if there is a string of length K that covers at most a number of points, the edge points of the string touching points on the X-axis are also covered.

Example:

Example 1: Input: arr = [1, 5, 13, 14, 15, 32, 43], k = 2 Output: 3

Example 2: Input: arr = [1, 5, 13, 14, 15, 32, 43], k = 5 Output: 3

Ii. Analysis of Ideas:

The length of the rope is an integer, so the end and end of the rope need to be covered at points.

Method one:

Each number in the array is regarded as the point covered by the rope tail, and the maximum point covered by the rope head is found. Example: arr = [1,3,7,9,11,13,14,15], k = 5

When the end is 1, the rope can move forward to -4, covering 1 point;

When the end is 5, the rope can move forward to 0, covering 2 points;

.

It can be seen that when the end is arr[I], the rope can reach arr[I]-k. So we just need to figure out the minimum value of arr greater than or equal to arr[I]-k, subtracting the minimum subscript and adding one is equal to the number of points covered by the rope. Use a variable to save the maximum number of points covered.

When I = 4, arr[I] = 11, a[I] -k = 6. Just look for the smallest value greater than 6 in the array and get its subscript, that is, the minimum subscript is 2. The coverage points are: I – 2 + 1 = 3.

One of the most core is to find the minimum subscript greater than a value, we can use binary to achieve.

Method 2:

Seeing the monotonicity of arrays, you can think of windowing to solve this problem. Define two left and right Pointers l, r, left and right without turning back. When r moves to the right, pay attention to whether the length between the covered head and tail is less than or equal to the rope length, that is, arr[r] -arr [l] <= k.

Iii. AC Code:

// Method 1:
function rope(arr, k) {
  let res = 1
  for (let i = 0; i < arr.length; i++) {
    let near = Dichotomous(arr, i, arr[i] - k) If arr[I]-k is greater than or equal to 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
}
// Method 2:
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
}
Copy the code

Iv. Summary:

On the basis of solving the problem, then optimize. The first method uses binary complexity O(nlogn), and the window method can reduce complexity to O(n).