Medium

题目描述

给你一个包含 n 个视频的流，每个视频用从 1 到 n 的不同数字表示，你需要将这些视频"上传"到服务器。你需要实现一个数据结构，在上传过程中的各个时间点计算最长上传前缀的长度。

如果范围 1 到 i（包含）内的所有视频都已上传到服务器，我们认为 i 是一个上传前缀。最长上传前缀是满足此定义的 i 的最大值。

实现 LUPrefix 类：

  • LUPrefix(int n) 为包含 n 个视频的流初始化对象。
  • void upload(int 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 <= 10^5
  • 1 <= video <= n
  • 所有 video 的值都是不同的。
  • 总共最多调用 upload 和 longest 方法 2 * 10^5 次。
  • 至少会调用一次 longest。

解题思路

这道题需要维护一个连续的上传前缀，关键在于如何高效地追踪当前最长的连续前缀长度。

思路分析：

最直观的方法是使用布尔数组标记视频是否已上传，每次查询时从头遍历找到最长连续前缀。但这样 longest() 操作的时间复杂度为 O(n)，在频繁查询时效率较低。

更优的方法是维护一个 maxPrefix 变量，表示当前最长连续前缀的长度。在 upload() 操作时，我们不仅标记视频已上传，还检查是否可以扩展当前的最长前缀。

具体策略：

  1. 使用布尔数组 uploaded 标记视频是否已上传
  2. 维护 maxPrefix 记录当前最长连续前缀长度
  3. 每次上传视频后，从 maxPrefix + 1 开始检查，看能否连续扩展前缀
  4. 这样避免了每次都从头遍历，大大提高了效率

当上传的视频正好是 maxPrefix + 1 时，我们可以立即扩展前缀；如果上传的是后面的视频，我们检查是否形成了更长的连续序列。

推荐解法： 使用布尔数组 + 动态维护最长前缀的方法，平衡了时间和空间复杂度。

代码实现

class LUPrefix {
private:
    vector<bool> uploaded;
    int maxPrefix;
    
public:
    LUPrefix(int n) : uploaded(n + 1, false), maxPrefix(0) {
    }
    
    void upload(int video) {
        uploaded[video] = true;
        
        // 从当前最长前缀的下一个位置开始检查
        while (maxPrefix + 1 < uploaded.size() && uploaded[maxPrefix + 1]) {
            maxPrefix++;
        }
    }
    
    int longest() {
        return maxPrefix;
    }
};

class LUPrefix:

    def __init__(self, n: int):
        self.uploaded = [False] * (n + 1)
        self.max_prefix = 0

    def upload(self, video: int) -> None:
        self.uploaded[video] = True
        
        # 从当前最长前缀的下一个位置开始检查
        while self.max_prefix + 1 < len(self.uploaded) and self.uploaded[self.max_prefix + 1]:
            self.max_prefix += 1

    def longest(self) -> int:
        return self.max_prefix

public class LUPrefix {
    private bool[] uploaded;
    private int maxPrefix;

    public LUPrefix(int n) {
        uploaded = new bool[n + 1];
        maxPrefix = 0;
    }
    
    public void Upload(int video) {
        uploaded[video] = true;
        
        // 从当前最长前缀的下一个位置开始检查
        while (maxPrefix + 1 < uploaded.Length && uploaded[maxPrefix + 1]) {
            maxPrefix++;
        }
    }
    
    public int Longest() {
        return maxPrefix;
    }
}

var LUPrefix = function(n) {
    this.uploaded = new Array(n + 1).fill(false);
    this.maxPrefix = 0;
};

LUPrefix.prototype.upload = function(video) {
    this.uploaded[video] = true;
    
    // 从当前最长前缀的下一个位置开始检查
    while (this.maxPrefix + 1 < this.uploaded.length && this.uploaded[this.maxPrefix + 1]) {
        this.maxPrefix++;
    }
};

LUPrefix.prototype.longest = function() {
    return this.maxPrefix;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(n)O(n)
upload均摊 O(1)O(1)
longestO(1)O(1)

说明： upload 操作的时间复杂度是均摊 O(1)，因为每个视频最多被检查一次来扩展前缀。在最坏情况下，单次 upload 可能需要 O(n) 时间，但总体来看是线性的。

相关题目