LeetCode 1970 你能穿过矩阵的最后一天思路二分答案 并查集1. 二分枚举最后可行天数2. 对当前天数标记前 mid 天被淹没的格子3. 遍历陆地格子用并查集连通上下左右增设顶部虚拟点、底部虚拟点4. 若顶部与底部连通说明可以穿越TypeScript 完整代码typescriptfunction latestDayToCross(row: number, col: number, cells: number[][]): number {// 上下左右方向const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]];// 二维坐标转一维编号const getIdx (x: number, y: number): number {return (x - 1) * col (y - 1) 1;};// 并查集class UnionFind {parent: number[];rank: number[];constructor(n: number) {this.parent Array.from({ length: n }, (_, i) i);this.rank new Array(n).fill(1);}find(x: number): number {if (this.parent[x] ! x) {this.parent[x] this.find(this.parent[x]);}return this.parent[x];}union(x: number, y: number): void {let fx this.find(x);let fy this.find(y);if (fx fy) return;if (this.rank[fx] this.rank[fy]) {this.parent[fx] fy;} else {this.parent[fy] fx;if (this.rank[fx] this.rank[fy]) {this.rank[fx];}}}}// 校验第 day 天是否可通行const canCross (day: number): boolean {const water: boolean[][] Array.from({ length: row 1 }, () new Array(col 1).fill(false));for (let i 0; i day; i) {const [x, y] cells[i];water[x][y] true;}const top 0;const bottom row * col 1;const uf new UnionFind(row * col 2);for (let i 1; i row; i) {for (let j 1; j col; j) {if (water[i][j]) continue;const cur getIdx(i, j);// 第一行连顶部if (i 1) uf.union(cur, top);// 最后一行连底部if (i row) uf.union(cur, bottom);// 四个方向连通for (const [dx, dy] of dirs) {const nx i dx;const ny j dy;if (nx 1 nx row ny 1 ny col !water[nx][ny]) {const neighbor getIdx(nx, ny);uf.union(cur, neighbor);}}}}return uf.find(top) uf.find(bottom);};// 二分let left 1;let right cells.length;let ans 0;while (left right) {const mid Math.floor((left right) / 2);if (canCross(mid)) {ans mid;left mid 1;} else {right mid - 1;}}return ans;}核心要点1. 虚拟节点- top 0 统一所有第一行陆地- bottom row*col1 统一所有最后一行陆地2. 坐标从 1 开始和题目 cells 输入下标保持一致避免换算错误3. 并查集带按秩合并路径压缩效率拉满4. 二分收缩最大合法天数最终得到答案复杂度- 时间O(\log N \times R \times C)- 空间O(R \times C)需要我再给一版反向并查集最优解法无需二分效率更高的 TS 代码吗