本文涉及的基础知识点
C++二分查找
树状数组
LeetCode2424. 最长上传前缀
给你一个 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 一次。
二分查找
我封装的树状数组的下标是从0开始的，故将video–。
二分类型：寻找尾端
Check函数的参数返回：[0,n]，一定有解。
Check 函数的实现：
{ 直接返回 t r u e 。 0 = = m i d t r e e A r r . S u m ( m i d − 1 ) = = m i d \begin{cases} 直接返回true。& 0 == mid \\ treeArr.Sum(mid-1) == mid \\ \end{cases} {直接返回true。treeArr.Sum(mid−1)==mid0==mid
代码
核心代码
template<class ELE = int >
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize + 1)
{
}
void Add(int index, ELE value)
{
index++;
while (index < m_vData.size())
{
m_vData[index] += value;
index += index & (-index);
}
}
ELE Sum(int index)//[0...index]之和
{
index++;
ELE ret = 0;
while (index)
{
ret += m_vData[index];
index -= index & (-index);
}
return ret;
}
ELE Sum() { return Sum(m_vData.size() - 2); }
ELE Get(int index)
{
return Sum(index) - Sum(index - 1);
}
private:
vector<ELE> m_vData;
};
template<class INDEX_TYPE>
class CBinarySearch
{
public:
CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
template<class _Pr>
INDEX_TYPE FindFrist( _Pr pr)
{
auto left = m_iMin - 1;
auto rightInclue = m_iMax;
while (rightInclue - left > 1)
{
const auto mid = left + (rightInclue - left) / 2;
if (pr(mid))
{
rightInclue = mid;
}
else
{
left = mid;
}
}
return rightInclue;
}
template<class _Pr>
INDEX_TYPE FindEnd( _Pr pr)
{
int leftInclude = m_iMin;
int right = m_iMax + 1;
while (right - leftInclude > 1)
{
const auto mid = leftInclude + (right - leftInclude) / 2;
if (pr(mid))
{
leftInclude = mid;
}
else
{
right = mid;
}
}
return leftInclude;
}
protected:
const INDEX_TYPE m_iMin, m_iMax;
};
class LUPrefix {
public:
LUPrefix(int n):m_treeArr(n), m_n(n){
}
void upload(int video) {
m_treeArr.Add(video - 1, 1);
}
int longest() {
auto Check = [&](int mid) {
if (0 == mid) { return true; }
return m_treeArr.Sum(mid - 1) == mid;
};
return CBinarySearch<int>(0, m_n).FindEnd(Check);
}
CTreeArr<int> m_treeArr;
int m_n;
};
单元测试
TEST_METHOD(TestMethod11)
{
LUPrefix server(4); // 初始化 4个视频的上传流
server.upload(3); // 上传视频 3 。
AssertEx(0, server.longest()); // 由于视频 1 还没有被上传，最长上传前缀是 0 。
server.upload(1); // 上传视频 1 。
AssertEx(1, server.longest()); // 前缀 [1] 是最长上传前缀，所以我们返回 1 。
server.upload(2); // 上传视频 2 。
AssertEx(3, server.longest()); // 前缀 [1,2,3] 是最长上传前缀，所以我们返回 3 。
}
二分+有序集合
本题从1开始，我们改成从0开始。
如果[0,x-1]都已经上传，那[0,x-2]也一定已经上传。故前缀是真，后缀是假。符合寻找尾端的前提。
参数范围[0,n]
Check函数：
有序集合s记录未上传的视频，初始值[0,n-1]。如果s.lower(mid) == s.begin()，表示[0,mid-1]都已经上传。
时间复杂度：O(nlogn)
class LUPrefix {
public:
LUPrefix(int n): m_n(n){
for (int i = 0; i < n; i++) {
m_s.emplace(i);
}
}
void upload(int video) {
m_s.erase(video-1);
}
int longest() {
auto Check = [&](int mid) {
return m_s.begin() == m_s.lower_bound(mid);
};
return CBinarySearch<int>(0, m_n).FindEnd(Check);
}
set<int> m_s;
int m_n;
};
滑动窗口
维护滑动窗口：[1,m_r] m_r+1没有上传，且[1,m_r]都已经上传。长度函数的返回值就是m_r。
上传的视频，m_has [ video ] = true。
当m_has[m_r+1]
m_r++
为了避免处理边界，m_has的长度为n+2。
时间复杂度：O(n)
代码
class LUPrefix {
public:
LUPrefix(int n){
m_has.assign(n + 2, false);
}
void upload(int video) {
m_has[video] = true;
while (m_has[m_r + 1]) { m_r++; }
}
int longest() {
return m_r;
}
vector<int> m_has;
int m_r=0;
};
