LeetCode 题解工作台
公交站间的距离
环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离， distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。 环线上的公交车都可以按顺时针和逆时针的方向行驶。 返回乘客从出发点 start 到目的地 de…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们可以先统计出公交车的总行驶距离 ，然后模拟公交车的行驶过程，从出发点开始，每次向右移动一站，直到到达目的地为止，记录下这个过程中的行驶距离 ，最后返回 和 $s - t$ 中的最小值即可。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1：
输入：distance = [1,2,3,4], start = 0, destination = 1 输出：1 解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
示例 2：
输入：distance = [1,2,3,4], start = 0, destination = 2 输出：3 解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
示例 3：
输入：distance = [1,2,3,4], start = 0, destination = 3 输出：4 解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
提示：
1 <= n <= 10^4distance.length == n0 <= start, destination < n0 <= distance[i] <= 10^4
解题思路
方法一：模拟
我们可以先统计出公交车的总行驶距离 ，然后模拟公交车的行驶过程，从出发点开始，每次向右移动一站，直到到达目的地为止，记录下这个过程中的行驶距离 ，最后返回 和 中的最小值即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def distanceBetweenBusStops(
self, distance: List[int], start: int, destination: int
) -> int:
s = sum(distance)
t, n = 0, len(distance)
while start != destination:
t += distance[start]
start = (start + 1) % n
return min(t, s - t)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) as we may traverse the array once to compute total distance and again for clockwise sum. Space complexity is O(1) since no additional arrays or structures are required beyond variables to track sums. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you handle circular array indices correctly.
- question_mark
Wants an efficient solution that avoids double-counting distances.
- question_mark
Looks for correct computation of both clockwise and counterclockwise paths.
常见陷阱
外企场景- error
Ignoring circular wraparound and causing index out-of-range errors.
- error
Summing only one direction and missing the shorter counter-direction path.
- error
Confusing start and destination indices, leading to incorrect distance calculations.
进阶变体
外企场景- arrow_right_alt
Compute distances for multiple pairs of stops efficiently using prefix sums.
- arrow_right_alt
Modify distances dynamically and query shortest paths repeatedly.
- arrow_right_alt
Handle weighted circular routes where distances change over time.