Medium

题目描述

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，对于所有 0 <= i < n - 1，从城市 i 到城市 i + 1 有一条单向道路。

queries[i] = [ui, vi] 表示新增一条从城市 ui 到城市 vi 的单向道路。在每次查询后，你需要找到从城市 0 到城市 n - 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 <= 500
  • 1 <= queries.length <= 500
  • queries[i].length == 2
  • 0 <= queries[i][0] < queries[i][1] < n
  • 1 < queries[i][1] - queries[i][0]
  • 查询中没有重复的道路。

解题思路

这道题需要我们在动态添加边的过程中，不断求解从起点到终点的最短路径。

核心思路：

  1. 初始状态下，图中只有相邻城市之间的边，即 i -> i+1，所以从 0 到 n-1 的最短距离为 n-1
  2. 每次添加新边后，图的结构发生变化，需要重新计算最短路径
  3. 由于图的规模较小（n ≤ 500），可以使用 BFS 来求解每次查询后的最短路径

算法步骤：

  1. 构建邻接表表示图
  2. 初始化图：添加所有 i -> i+1 的边
  3. 对于每个查询：
    • 添加新边到图中
    • 使用 BFS 从节点 0 开始搜索，找到到节点 n-1 的最短距离
    • 将结果加入答案数组

时间复杂度分析：

  • 每次 BFS 的时间复杂度为 O(V + E) = O(n + 查询数)
  • 总时间复杂度为 O(查询数 × n)，在给定约束下是可接受的

这个解法简单直观，适合处理动态图的最短路径问题。

代码实现

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> graph(n);
        
        // 初始化图：添加相邻城市的边
        for (int i = 0; i < n - 1; i++) {
            graph[i].push_back(i + 1);
        }
        
        vector<int> result;
        
        for (auto& query : queries) {
            int u = query[0], v = query[1];
            graph[u].push_back(v);
            
            // BFS 求最短路径
            queue<int> q;
            vector<int> dist(n, -1);
            q.push(0);
            dist[0] = 0;
            
            while (!q.empty()) {
                int curr = q.front();
                q.pop();
                
                if (curr == n - 1) {
                    break;
                }
                
                for (int next : graph[curr]) {
                    if (dist[next] == -1) {
                        dist[next] = dist[curr] + 1;
                        q.push(next);
                    }
                }
            }
            
            result.push_back(dist[n - 1]);
        }
        
        return result;
    }
};

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        from collections import deque
        
        graph = [[] for _ in range(n)]
        
        # 初始化图：添加相邻城市的边
        for i in range(n - 1):
            graph[i].append(i + 1)
        
        result = []
        
        for u, v in queries:
            graph[u].append(v)
            
            # BFS 求最短路径
            queue = deque([0])
            dist = [-1] * n
            dist[0] = 0
            
            while queue:
                curr = queue.popleft()
                
                if curr == n - 1:
                    break
                
                for next_node in graph[curr]:
                    if dist[next_node] == -1:
                        dist[next_node] = dist[curr] + 1
                        queue.append(next_node)
            
            result.append(dist[n - 1])
        
        return result

public class Solution {
    public int[] ShortestDistanceAfterQueries(int n, int[][] queries) {
        List<int>[] graph = new List<int>[n];
        
        // 初始化图：添加相邻城市的边
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        for (int i = 0; i < n - 1; i++) {
            graph[i].Add(i + 1);
        }
        
        List<int> result = new List<int>();
        
        foreach (var query in queries) {
            int u = query[0], v = query[1];
            graph[u].Add(v);
            
            // BFS 求最短路径
            Queue<int> queue = new Queue<int>();
            int[] dist = new int[n];
            for (int i = 0; i < n; i++) {
                dist[i] = -1;
            }
            
            queue.Enqueue(0);
            dist[0] = 0;
            
            while (queue.Count > 0) {
                int curr = queue.Dequeue();
                
                if (curr == n - 1) {
                    break;
                }
                
                foreach (int next in graph[curr]) {
                    if (dist[next] == -1) {
                        dist[next] = dist[curr] + 1;
                        queue.Enqueue(next);
                    }
                }
            }
            
            result.Add(dist[n - 1]);
        }
        
        return result.ToArray();
    }
}

var shortestDistanceAfterQueries = function(n, queries) {
    const graph = Array.from({length: n}, () => []);
    
    // Initialize the graph with consecutive roads
    for (let i = 0; i < n - 1; i++) {
        graph[i].push(i + 1);
    }
    
    const bfs = () => {
        const queue = [0];
        const visited = new Array(n).fill(false);
        visited[0] = true;
        let distance = 0;
        
        while (queue.length > 0) {
            const size = queue.length;
            for (let i = 0; i < size; i++) {
                const node = queue.shift();
                if (node === n - 1) {
                    return distance;
                }
                
                for (const neighbor of graph[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.push(neighbor);
                    }
                }
            }
            distance++;
        }
        
        return -1;
    };
    
    const result = [];
    
    for (const [u, v] of queries) {
        graph[u].push(v);
        result.push(bfs());
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(queries.length × n)每次查询需要进行一次 BFS，BFS 的时间复杂度为 O(V + E)，在最坏情况下为 O(n)
空间复杂度O(n + queries.length)图的邻接表存储空间 O(n + queries.length)，BFS 过程中的队列和距离数组空间 O(n)