公交站间的距离

难度: Easy

环形公交路线上有 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^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Submission

运行时间: 20 ms

内存: 17.3 MB

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        totaldistance = 0
        if start > destination:
            start,destination = destination, start
        totaldistance = sum(distance[start:destination])
        total = sum(distance)
        return min(totaldistance,total - totaldistance)

Explain

首先，该题解采取的思路是先确保start小于destination，如果不是，则交换两者的值。接下来，计算从起点到终点的顺时针距离，即数组distance中从start到destination的子数组的和。总距离是环形公交路线的总距离，即distance数组的所有元素之和。最后，返回顺时针距离与总距离减去顺时针距离（即逆时针距离）的较小值，这是因为公交车可以顺时针或逆时针行驶，我们需要的是最短距离。

时间复杂度: O(n)

空间复杂度: O(1)

# 给定的Python代码实现了解决问题的功能

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        # 确保start小于destination，如果不是，则交换它们
        if start > destination:
            start, destination = destination, start
        # 计算从start到destination的顺时针距离
        totaldistance = sum(distance[start:destination])
        # 计算环形公交路线的总距离
        total = sum(distance)
        # 返回顺时针距离和逆时针距离中的较小值
        return min(totaldistance, total - totaldistance)

Explore

在算法中首先确保`start`小于`destination`是为了简化顺时针距离的计算。如果不先调整，当`start`大于`destination`时，顺时针距离的计算将需要考虑跨越数组的末尾到开头的情况，这会增加算法的复杂度。通过交换，可以直接使用数组切片从`start`到`destination`计算顺时针距离，从而避免处理数组的环形特性。

使用`total - totaldistance`计算逆时针距离是因为这种方法可以更快地得到结果。直接计算从`destination`到`start`的距离需要处理数组的环形结构，可能涉及到分段计算（从`destination`到数组末尾加上从数组开头到`start`），这在代码实现上比简单的总距离减去顺时针距离更复杂。而`total - totaldistance`只需要一次数组的完整求和和一次简单的减法，因此更高效。

如果`start`和`destination`相等，表示起点和终点是同一个位置，因此顺时针和逆时针距离都应该是0。题解中通过交换`start`和`destination`保证了它们的大小关系，但没有明确指出相等情况的处理。然而，在`start`等于`destination`的情况下，`distance[start:destination]`将返回空数组，其和自然为0，因此算法仍然正确地返回了0作为距离。

当前算法的时间复杂度主要取决于数组`distance`的大小，因为需要计算数组的总和以及子数组的和。如果数组非常大，这些操作将会消耗较多的计算资源。如果要优化，可以考虑预先计算环形数组的累积和，将其存储在另一个数组中，这样任何子段的和都可以通过简单的减法从预计算值中获取，从而将求和操作的复杂度从线性降低到常数时间。这种方法需要更多的初始化时间和空间，但可以显著减少每次查询的时间成本。