What is the main pattern behind Longest Uploaded Prefix?

The primary pattern is binary search over the valid answer space, ensuring efficient prefix computation without scanning all videos.

Can uploads be handled out of order?

Yes, the solution must support uploads in any order, tracking each video independently to update the longest prefix.

What data structures are most useful for this problem?

Boolean arrays, Hash Tables, and Union-Find structures efficiently track uploaded videos and compute the longest prefix.

How does binary search optimize longest prefix queries?

Instead of scanning sequentially, binary search finds the highest index where all videos are uploaded, reducing query time.

What is a common mistake when implementing LUPrefix?

A frequent error is assuming uploads are sequential and failing to handle gaps, which breaks the longest prefix calculation.

#2424

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最长上传前缀

给你一个 n 个视频的上传序列，每个视频编号为 1 到 n 之间的不同数字，你需要依次将这些视频上传到服务器。请你实现一个数据结构，在上传的过程中计算最长上传前缀。如果闭区间 1 到 i 之间的视频全部都已经被上传到服务器，那么我们称 i 是上传前缀。最长上传前缀指的是符合定义的 i 中…

哈希表二分查找并查集设计树状数组

题目描述

给你一个 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 <= 10⁵
1 <= video <= 10⁵
video 中所有值 互不相同 。
upload 和 longest 总调用 次数至多不超过 2 * 10⁵ 次。
至少会调用 longest 一次。

lightbulb

解题思路

方法一：模拟

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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()

speed

复杂度分析

指标	值
时间	complexity ranges from O(1) per upload to O(log n) per longest query if using binary search or union-find path compression. Space complexity is O(n) for tracking uploaded videos.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about handling out-of-order uploads efficiently.
question_mark
Probe whether prefix computation can avoid scanning all videos.
question_mark
Check if candidate recognizes binary search over answer space pattern.

warning

常见陷阱

外企场景

error
Iterating from 1 to n for each query leads to TLE with large n.
error
Forgetting to mark videos as uploaded correctly in the tracking structure.
error
Assuming uploads are sequential and failing with out-of-order inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Query the number of missing videos in a range instead of the prefix.
arrow_right_alt
Support batch uploads and compute longest prefix after each batch.
arrow_right_alt
Return all longest prefixes after a series of uploads instead of single queries.

help

常见问题

外企场景

继续练习

#2426 满足不等式的数对数目 #2353 设计食物评分系统 #2349 设计数字容器系统