题目链接
分析
本题比 3243. 新增道路查询后的最短距离 I 多出一个额外条件，对于任意两个额外道路$[u,v]$, $[u’,v’]$，均不会存在 $u < u’ < v < v’$，即道路不存在交叉
故使用贪心维护每个城市可以去到的最右端城市
定义 $nxt[i]$ 为第 $i$ 个城市可以去到的最右端城市，$cnt$
对于每个查询 $[l,r]$
- 如果被之前已经连过的边包含，do nothing
- 否则，令 $nxt[l] = r$，区间 $[nxt[l], r - 1]$ 可不进行计算（已经被更好的路线包围），将其标记为 $r$
维护一个 $cnt$ 变量，表示剩下的道路数量，每次标记时令 $cnt - 1$
代码实现
class Solution {
public:
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<int> nxt(n, 0), ans;
iota(nxt.begin(), nxt.end(), 1); // 对 nxt 数组顺序赋值，每次递增1
int cnt = n - 1;
for(auto &query : queries)
{
int l = query[0], r = query[1];
while(nxt[l] < r)
{
int t = nxt[l];
nxt[l] = r;
l = t;
cnt--;
}
ans.emplace_back(cnt);
}
return ans;
}
};
复杂度分析
- 时间复杂度：$O(n + q)$，$q$ 为查询数组长度
- 空间复杂度：$O(n)$
