3244：新增道路查询后的最短距离 II（2270 分）

力扣第 409 场周赛第 3 题

题目

给你一个整数 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：

示例 2：

提示:

• 3 <= n <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• 查询中不存在重复的道路。
• 不存在两个查询都满足 i != j 且 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

分析

• 由于道路不交叉，那么添加道路 (u,v) 后，在 u,v 之间的节点就无用了，直接删掉
• 用数组模拟链表的删除即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        R = list(range(1,n))
        res,s = [],n-1
        for i,j in queries:
            while R[i]<j:
                R[i],i = j,R[i]
                s -= 1
            res.append(s)
        return res

89 ms