LeetCode 题解工作台
新增道路查询后的最短距离 II
给你一个整数 n 和一个二维整数数组 queries 。 有 n 个城市，编号从 0 到 n - 1 。初始时，每个城市 i 都有一条 单向 道路通往城市 i + 1 （ 0 ）。 queries[i] = [u i , v i ] 表示新建一条从城市 u i 到城市 v i 的 单向 道路。每次查…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
我们定义一个长度为 $n - 1$ 的数组 ，其中 表示从城市 可以到达的下一个城市的编号。初始时 $\textit{nxt}[i] = i + 1$。 对于每次查询 $[u, v]$，如果此前已经连通了 和 ，且 $u' <= u < v <= v'$，那么我们可以跳过这次查询。否则，我们需要将 到 $nxt[v - 1]$ 这些城市的下一个城市编号设置为 ，并将 设置为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
所有查询中不会存在两个查询都满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
示例 1：
输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：
新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。
示例 2：
输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。
提示:
3 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]- 查询中不存在重复的道路。
- 不存在两个查询都满足
i != j且queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。
解题思路
方法一：贪心 + 记录跳转位置
我们定义一个长度为 的数组 ，其中 表示从城市 可以到达的下一个城市的编号。初始时 。
对于每次查询 ，如果此前已经连通了 和 ，且 ，那么我们可以跳过这次查询。否则，我们需要将 到 这些城市的下一个城市编号设置为 ，并将 设置为 。
在这个过程中，我们维护一个变量 ，表示从城市 到城市 的最短路径的长度。初始时 。每一次，如果我们将 这些城市的下一个城市编号设置为 ，那么 就会减少 。
时间复杂度 ，空间复杂度 。其中 和 分别是城市数量和查询数量。
class Solution:
def shortestDistanceAfterQueries(
self, n: int, queries: List[List[int]]
) -> List[int]:
nxt = list(range(1, n))
ans = []
cnt = n - 1
for u, v in queries:
if 0 < nxt[u] < v:
i = nxt[u]
while i < v:
cnt -= 1
nxt[i], i = 0, nxt[i]
nxt[u] = v
ans.append(cnt)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate can handle graph traversal problems with dynamic updates.
- question_mark
Look for understanding of greedy algorithms and how they can be applied to graph-related problems.
- question_mark
Assess how efficiently the candidate manages graph updates to avoid excessive recomputation.
常见陷阱
外企场景- error
Not updating the graph efficiently, leading to redundant recalculations of the shortest path.
- error
Forgetting to optimize the process for larger inputs, leading to timeouts.
- error
Misunderstanding the greedy choice strategy, which may result in suboptimal path calculations.
进阶变体
外企场景- arrow_right_alt
Add more roads at once rather than one at a time, requiring batch processing.
- arrow_right_alt
Allow roads to be bi-directional, adding complexity to the shortest path calculations.
- arrow_right_alt
Introduce more constraints such as varying road lengths, instead of assuming unit length roads.