Hard

题目描述

给你一个整数 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 的道路后，最短路径长度仍为 1。

提示：

  • 3 <= n <= 10^5
  • 1 <= queries.length <= 10^5
  • 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] 时：

  1. 移除所有被新道路完全覆盖的旧道路（即起点 >= u 且终点 <= v 的道路）
  2. 添加新道路到集合中
  3. 计算当前最短路径长度

具体实现：

  • 使用 set 维护有效道路的有序集合
  • 对于每个查询，先清理被覆盖的道路，再添加新道路
  • 最短路径长度 = n - 1 - (所有有效道路节省的步数之和)

这种方法比每次都跑 BFS 要高效得多，时间复杂度从 O(m×n) 降低到 O(m×log m)，其中 m 是查询数量。

代码实现

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        set<pair<int, int>> roads;
        vector<int> result;
        
        for (auto& query : queries) {
            int u = query[0], v = query[1];
            
            // 移除被新道路覆盖的旧道路
            auto it = roads.lower_bound({u, 0});
            while (it != roads.end() && it->first >= u && it->second <= v) {
                it = roads.erase(it);
            }
            
            // 添加新道路
            roads.insert({u, v});
            
            // 计算当前最短距离
            int saved = 0;
            for (auto& road : roads) {
                saved += road.second - road.first - 1;
            }
            result.push_back(n - 1 - saved);
        }
        
        return result;
    }
};

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        from sortedcontainers import SortedSet
        
        roads = SortedSet()
        result = []
        
        for u, v in queries:
            # 移除被新道路覆盖的旧道路
            to_remove = []
            for start, end in roads:
                if start >= u and end <= v:
                    to_remove.append((start, end))
            
            for road in to_remove:
                roads.remove(road)
            
            # 添加新道路
            roads.add((u, v))
            
            # 计算当前最短距离
            saved = sum(end - start - 1 for start, end in roads)
            result.append(n - 1 - saved)
        
        return result

public class Solution {
    public int[] ShortestDistanceAfterQueries(int n, int[][] queries) {
        var roads = new SortedSet<(int, int)>();
        var result = new List<int>();
        
        foreach (var query in queries) {
            int u = query[0], v = query[1];
            
            // 移除被新道路覆盖的旧道路
            var toRemove = new List<(int, int)>();
            foreach (var road in roads) {
                if (road.Item1 >= u && road.Item2 <= v) {
                    toRemove.Add(road);
                }
            }
            
            foreach (var road in toRemove) {
                roads.Remove(road);
            }
            
            // 添加新道路
            roads.Add((u, v));
            
            // 计算当前最短距离
            int saved = 0;
            foreach (var road in roads) {
                saved += road.Item2 - road.Item1 - 1;
            }
            result.Add(n - 1 - saved);
        }
        
        return result.ToArray();
    }
}

var shortestDistanceAfterQueries = function(n, queries) {
    const roads = new Set();
    const result = [];
    
    for (const [u, v] of queries) {
        // 移除被新道路覆盖的旧道路
        const toRemove = [];
        for (const road of roads) {
            const [start, end] = road.split(',').map(Number);
            if (start >= u && end <= v) {
                toRemove.push(road);
            }
        }
        
        for (const road of toRemove) {
            roads.delete(road);
        }
        
        // 添加新道路
        roads.add(`${u},${v}`);
        
        // 计算当前最短距离
        let saved = 0;
        for (const road of roads) {
            const [start, end] = road.split(',').map(Number);
            saved += end - start - 1;
        }
        result.push(n - 1 - saved);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(m × log m)
空间复杂度O(m)

其中 m 为查询数量。每次查询需要在有序集合中查找和删除操作，单次操作时间复杂度为 O(log m)。