lc2424
单指针
用一个布尔数组标记已上传的视频，每次上传后更新当前连续上传前缀的最大长度，直接返回这个长度即可
class LUPrefix {
public:
int n;
bool * visited;
int ID;
LUPrefix(int n) {
this->n = n;
visited = new bool[n + 1];
for (int i = 0; i < n + 1; i ++){
visited[i] = false;
}
ID = 0;
}
void upload(int video) {
visited[video] = true;
while (ID + 1 <= n && visited[ID + 1] == true)
ID ++;
}
int longest() {
return ID;
}
};
按秩合并是启发式合并在并查集里的具体实现
按秩合并的“秩”（通常是树的高度或节点数）是启发式合并选择合并方向的核心依据，本质是通过让小树合并到大树下，避免并查集退化成链表，保证操作的时间复杂度接近常数
class DSU {
private:
vector<int> parent;
vector<int> rank;
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 1);
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
if (rank[fx] < rank[fy]) parent[fx] = fy;
else {
parent[fy] = fx;
if (rank[fx] == rank[fy]) rank[fx]++;
}
}
};
lc1292
二维前缀和
预处理: sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
求解: int t = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
二维前缀和快速计算矩阵内正方形子矩阵的和，遍历所有可能的正方形，找出不超过阈值的最大边长
class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold)
{
vector<vector<int>> sum;
int m = mat.size(), n = mat[0].size();
sum.resize(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
}
}
int mx=0;
for(int r1=0;r1<m;r1++)
{
for(int c1=0;c1<n;c1++)
{
for(int k=mx+1; r1+k<=m && c1+k<=n; k++)
{
int r2 = r1 + k, c2 = c1 + k;
int t = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
if(t <= threshold)
mx = k;
else
break;
}
}
}
return mx;
}
};
