基于微秒级有序时间戳向量，求同时间段元素最大数量的高效方法

你的原始思路如果是逐个遍历后用线性查找定位同时间段的最后一个元素，时间复杂度是O(n²)，效率较低；如果改用二分查找，时间复杂度能降到O(n log n)，但还有更优的O(n)时间复杂度方案——利用数组已排序的特性，用**滑动窗口（双指针）**实现。

具体实现逻辑 #

因为时间戳向量是按微秒递增排序的，所以可以用两个指针维护一个窗口，窗口内的所有元素都满足「与窗口左边界元素的时间差≤1秒（即1e6微秒）」：

• 初始化左指针i=0，最大长度max_len=0；
• 遍历右指针j从0到n-1：
  1. 当vec[j] - vec[i] > 1e6时，不断将左指针i右移，直到窗口内元素满足时间差要求；
  2. 计算当前窗口长度current_len = j - i + 1，如果大于max_len就更新max_len；
• 遍历结束后，max_len就是元素数量最多的子向量长度。

为什么这个方法更优？ #

每个元素最多被左、右指针各访问一次，整个过程只需要遍历数组一次，时间复杂度是O(n)，是该问题的最优时间复杂度（因为至少要遍历所有元素一次）。

对比其他思路 #

• 线性查找定位：O(n²)，最坏情况每个元素都要遍历后面所有元素，效率最低；
• 二分查找定位：O(n log n)，对每个元素用二分找最大的满足时间差的下标，比线性查找好，但不如滑动窗口的线性时间高效；
• 滑动窗口：O(n)，完全利用数组有序的特性，避免重复计算，是最优解。

内容的提问来源于stack exchange，提问作者Ted Zach