算法题-线段点最多覆盖

发表于 更新于 分类于
本文字数： 388 阅读时长 ≈ 1 分钟

题目

  1. 给定一个有序数组 arr ，代表坐落在 X 轴上的点
  2. 给定一个正数K，代表绳子的长度
  3. 返回绳子最多压中几个点，即使绳子边缘处被盖住了也算盖住

思路

  1. 采用左右指针，指针为数组下标
  2. 右指针 - 左指针 = 当前覆盖点数
  3. 右指针指向的值 - 左指针指向的值代表坐落在 X 轴上的点的跨度，要小于对于绳子长度

解

1
2
3
4
5
6
7
8
9
10
11
private static int mySolution(int[] arr, int l) {
    int left = 0, right = 0;
    int max = 0;
    while (left < arr.length) {
        while (right < arr.length && arr[right] - arr[left] <= l) {
            right++;
        }
        max = Math.max(max, right - left++);
    }
    return max;
}