引题
给定一个有序数组arr，代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n-1]。给定一个正数L，代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
思路
1. 以数组中第一个点为绳子的开头，往后一个一个遍历，看能够覆盖多少个点。以第二个点为开头，往后依次遍历，记录覆盖的点的个数，依次遍历，寻找最大值。
2. 采用二分思想，当数组中每个点都为绳子的结尾，绳子长度为L时，寻找开头的位置。如arr[3]=9，L=9，寻找>=arr[3]-L 的最左边的点的位置。
3. 以A为开头，最后一个不超过L的位置为结尾B，以第一个点为A，找满足条件的最远的B的位置，然后将A往前移动一个位置，B从当前位置继续往下遍历，寻找满足的结尾。
代码
import java.util.Arrays;
public class Code01_CordCoverMaxPoint {
public static int maxPoint1(int[] arr, int L) {
int res = 1;
for (int i = 0; i < arr.length; i++) {
int nearest = nearestIndex(arr, i, arr[i] - L);
res = Math.max(res, i - nearest + 1);
}
return res;
}
public static int nearestIndex(int[] arr, int R, int value) {
int L = 0;
int index = R;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
public static int maxPoint2(int[] arr, int L) {
int left = 0;
int right = 0;
int N = arr.length;
int max = 0;
while (left < N) {
while (right < N && arr[right] - arr[left] <= L) {
right++;
}
max = Math.max(max, right - (left++));
}
return max;
}
// for test
public static int test(int[] arr, int L) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
int pre = i - 1;
while (pre >= 0 && arr[i] - arr[pre] <= L) {
pre--;
}
max = Math.max(max, i - pre);
}
return max;
}
// for test
public static int[] generateArray(int len, int max) {
int[] ans = new int[(int) (Math.random() * len) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = (int) (Math.random() * max);
}
Arrays.sort(ans);
return ans;
}
public static void main(String[] args) {
int len = 100;
int max = 1000;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
int L = (int) (Math.random() * max);
int[] arr = generateArray(len, max);
int ans1 = maxPoint1(arr, L);
int ans2 = maxPoint2(arr, L);
int ans3 = test(arr, L);
if (ans1 != ans2 || ans2 != ans3) {
System.out.println("oops!");
break;
}
}
}
}
随堂练习
数轴上有 N 个点，求一条长度为 K 的线段最多覆盖多少个点？，此处我们认为长度为1的线段最多可以覆盖1个点。
数据范围：1≤n≤30000，1≤k≤1000
数据描述：
第一行N和K，表示点数和线段长度
第二行N个数，表示N个点的坐标
输出描述：
输出一个数，最多覆盖的点数
示例1
输入
5 3
1 2 3 4 5
输出
3
示例2
输入
5 3
1 3 5 7 9
输出
2
Java代码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static int maxPoint(int[] arr, int L) {
int left = 0;
int right = 0;
int N = arr.length;
int max = 0;
while (left < N) {
while (right < N && arr[right] - arr[left] < L) {
right++;
}
max = Math.max(max, right - (left++));
}
return max;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int l = sc.nextInt();
int [] arr = new int [n];
for(int i = 0 ; i < n ; i++){
arr[i] = sc.nextInt();
}
System.out.println(maxPoint(arr, l));
}
}
C++代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main()
{
int n;
int k;
cin>>n>>k;
int w[100010];
for(int i = 0; i < n; i++)
cin>>w[i];
int l = 0;
int m = 0;
for(int i=0; i<n; i++)
{
while(w[i]-w[l]>=k)
{
l++;
}
m = max(m,i-l+1);
}
cout<<m<<endl;;
return 0;
}
Python代码
n,k= input().split()
n=int(n)
k=int(k)
N=input().split()
ln=len(N)
l=0
m=0
for i in range(0,ln):
while int(N[i])-int(N[l])>=k:
l+=1
m=max(m,i-l+1)
print(m)
