数轴上从左到右有n个点a[0],a[1]...a[n-1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。

来源:V型知识库 2018年12月30日 22:52 浏览:2322

解析:

O(n^2)枚举自然都能能想到。

给个O(n)的想法。

以每个i为起点,只希望覆盖更多的点。

注意每次循环best和i都只增不减,尽管两个循环,复杂度还是O(n)的。

int calculate(int *a, int n, int L) {     
 int best = 0;
 for (int i = 0; i + best < n; ++i) {
for (; (i + best < n) && (a[i + best] - a[i] <= L); ++best)        ;   
 }   
 return best;
}


上一篇:  js join


下一篇:  什么是分布式数据库?