数轴上从左到右有n各点a[0], a[1], ……,a[n -1]给萣一根长度为L的子,求子最多能覆盖其中的几个点
遍历所有区间跟子L比较。
i遍历区间起点j遍历区间终点。
每个数最多遍历2遍因此时間复杂度为O(n)。
对于这个算法某网友给了一个形象的比喻:
就好像一条长度为L的蛇。头伸不过去的话就把尾巴缩过来最多只需要走一次,就知道能覆盖几个点
如果本方法有什么问题欢迎指正。如果有更好的方法欢迎指导。