最长上传前缀

标签: 并查集 设计 树状数组 线段树 二分查找 有序集合 堆（优先队列）

难度: Medium

给你一个 n 个视频的上传序列，每个视频编号为 1 到 n 之间的 不同 数字，你需要依次将这些视频上传到服务器。请你实现一个数据结构，在上传的过程中计算 最长上传前缀 。

如果 闭区间 1 到 i 之间的视频全部都已经被上传到服务器，那么我们称 i 是上传前缀。最长上传前缀指的是符合定义的 i 中的 最大值 。

请你实现 LUPrefix 类：

  • LUPrefix(int n) 初始化一个 n 个视频的流对象。
  • void upload(int video) 上传 video 到服务器。
  • int longest() 返回上述定义的 最长上传前缀 的长度。

示例 1：

输入：
["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"]
[[4], [3], [], [1], [], [2], []]
输出：
[null, null, 0, null, 1, null, 3]

解释：
LUPrefix server = new LUPrefix(4);   // 初始化 4个视频的上传流
server.upload(3);                    // 上传视频 3 。
server.longest();                    // 由于视频 1 还没有被上传，最长上传前缀是 0 。
server.upload(1);                    // 上传视频 1 。
server.longest();                    // 前缀 [1] 是最长上传前缀，所以我们返回 1 。
server.upload(2);                    // 上传视频 2 。
server.longest();                    // 前缀 [1,2,3] 是最长上传前缀，所以我们返回 3 。

提示：

  • 1 <= n <= 105
  • 1 <= video <= 105
  • video 中所有值 互不相同 。
  • upload 和 longest 总调用 次数至多不超过 2 * 105 次。
  • 至少会调用 longest 一次。

Submission

运行时间: 300 ms

内存: 65.3 MB

class LUPrefix:
    def __init__(self, n: int):
        self.calcu=[0]*n
        self.count=0
    def upload(self, video: int) -> None:
        self.calcu[video-1]=1
        while(self.count<len(self.calcu) and self.calcu[self.count]==1 ):
            self.count+=1
    def longest(self) -> int:
        return self.count

Explain

此题解主要使用一个数组 `calcu` 来跟踪哪些视频已上传，其中数组的索引对应视频编号减一（因为视频编号从1开始，数组索引从0开始）。当上传视频时，对应的数组位置被设置为1。为了高效跟踪最长上传前缀，使用了一个额外的变量 `count` 来记录当前最长上传前缀的长度。每次 `upload` 操作后，从 `count` 开始检查，如果连续的视频都已上传，则 `count` 增加，反之停止。这样，`longest` 方法只需返回 `count` 的值即可。

时间复杂度: O(n) 平摊时间复杂度，其中 n 是操作总数

空间复杂度: O(n)

class LUPrefix:
    def __init__(self, n: int):
        self.calcu = [0] * n  # 初始化标记数组，0表示未上传，1表示已上传
        self.count = 0  # 初始化最长上传前缀为0

    def upload(self, video: int) -> None:
        self.calcu[video - 1] = 1  # 标记视频已上传
        # 更新最长上传前缀
        while self.count < len(self.calcu) and self.calcu[self.count] == 1:
            self.count += 1

    def longest(self) -> int:
        return self.count  # 直接返回当前最长上传前缀长度

Explore

在每次调用`upload`方法时更新`count`并不会显著影响性能，因为`count`的更新直接依赖于上传的视频是否连续。尽管`while`循环可能在某些情况下执行多次（例如连续上传多个视频），但每个视频编号最多只被检查一次。因此，整体性能影响是线性的，与视频总数成正比。此外，这种方法可以避免在每次调用`longest`时进行重复的、可能更耗时的计算。

选择在每次`upload`后立即更新`count`是为了优化`longest`方法的效率，使其能够在O(1)时间复杂度内返回结果。如果延迟更新直到调用`longest`，那么每次调用`longest`都可能需要遍历整个`calcu`数组来计算最长上传前缀，特别是在高频调用的场景下这将非常低效。立即更新保证了数据的即时性和准确性，同时使得`longest`方法的调用非常高效。

在这种非连续上传的场景下，算法依然能够正确处理并返回当前最长的连续上传前缀。例如在上传了1, 2, 4, 5的情况下，由于3号视频未上传，`count`会停留在2，这意味着最长连续上传前缀的长度是2。算法设计确保只有当一个序列完全连续时，`count`才会增加，确保了其准确性和鲁棒性。