Question

2424. 最长上传前缀

English Version

题目描述

给你一个 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 一次。

解法

方法一：模拟

我们用变量 $r$ 记录当前的最长上传前缀，用数组或哈希表 $s$ 记录已经上传的视频。

每次上传视频 video 时，将 s[video] 置为 true，然后循环判断 s[r + 1] 是否为 true，如果是，则更新 $r$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为视频总数。

class LUPrefix:
  def __init__(self, n: int):
    self.r = 0
    self.s = set()

  def upload(self, video: int) -> None:
    self.s.add(video)
    while self.r + 1 in self.s:
      self.r += 1

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


# Your LUPrefix object will be instantiated and called as such:
# obj = LUPrefix(n)
# obj.upload(video)
# param_2 = obj.longest()

class LUPrefix {
  private int r;
  private Set<Integer> s = new HashSet<>();

  public LUPrefix(int n) {
  }

  public void upload(int video) {
    s.add(video);
    while (s.contains(r + 1)) {
      ++r;
    }
  }

  public int longest() {
    return r;
  }
}

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix obj = new LUPrefix(n);
 * obj.upload(video);
 * int param_2 = obj.longest();
 */

class LUPrefix {
public:
  LUPrefix(int n) {
  }

  void upload(int video) {
    s.insert(video);
    while (s.count(r + 1)) {
      ++r;
    }
  }

  int longest() {
    return r;
  }

private:
  int r = 0;
  unordered_set<int> s;
};

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix* obj = new LUPrefix(n);
 * obj->upload(video);
 * int param_2 = obj->longest();
 */

type LUPrefix struct {
  r int
  s []bool
}

func Constructor(n int) LUPrefix {
  return LUPrefix{0, make([]bool, n+1)}
}

func (this *LUPrefix) Upload(video int) {
  this.s[video] = true
  for this.r+1 < len(this.s) && this.s[this.r+1] {
    this.r++
  }
}

func (this *LUPrefix) Longest() int {
  return this.r
}

/**
 * Your LUPrefix object will be instantiated and called as such:
 * obj := Constructor(n);
 * obj.Upload(video);
 * param_2 := obj.Longest();
 */