Easy

题目描述

一辆公交车有 n 个站点，编号从 0 到 n - 1，这些站点形成一个圆圈。我们知道所有相邻站点之间的距离，其中 distance[i] 是站点 i 和站点 (i + 1) % n 之间的距离。

公交车可以沿两个方向行驶，即顺时针和逆时针。

返回给定起点和终点站点之间的最短距离。

示例 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

解题思路

解题思路

这是一个环形公交线路的最短路径问题。由于站点形成一个圆圈，从起点到终点有两条可能的路径：

  1. 顺时针路径：从 start 按索引递增方向到达 destination
  2. 逆时针路径：从 start 按索引递减方向（绕一圈）到达 destination

关键观察：由于是圆形路线，逆时针路径的距离等于总距离减去顺时针路径的距离。

算法步骤：

  1. 确保 start < destination，如果不是则交换两者（因为距离是双向的）
  2. 计算顺时针路径距离：从 start 到 destination-1 的所有 distance[i] 之和
  3. 计算总距离：所有 distance[i] 的和
  4. 逆时针距离 = 总距离 - 顺时针距离
  5. 返回两者的最小值

这种方法避免了复杂的索引计算，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        if (start > destination) {
            swap(start, destination);
        }
        
        int clockwise = 0;
        int total = 0;
        
        for (int i = 0; i < distance.size(); i++) {
            if (i >= start && i < destination) {
                clockwise += distance[i];
            }
            total += distance[i];
        }
        
        int counterclockwise = total - clockwise;
        return min(clockwise, counterclockwise);
    }
};

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

public class Solution {
    public int DistanceBetweenBusStops(int[] distance, int start, int destination) {
        if (start > destination) {
            int temp = start;
            start = destination;
            destination = temp;
        }
        
        int clockwise = 0;
        int total = 0;
        
        for (int i = 0; i < distance.Length; i++) {
            if (i >= start && i < destination) {
                clockwise += distance[i];
            }
            total += distance[i];
        }
        
        int counterclockwise = total - clockwise;
        return Math.Min(clockwise, counterclockwise);
    }
}

var distanceBetweenBusStops = function(distance, start, destination) {
    if (start > destination) {
        [start, destination] = [destination, start];
    }
    
    let clockwise = 0;
    let total = 0;
    
    for (let i = 0; i < distance.length; i++) {
        if (i >= start && i < destination) {
            clockwise += distance[i];
        }
        total += distance[i];
    }
    
    const counterclockwise = total - clockwise;
    return Math.min(clockwise, counterclockwise);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历整个距离数组一次
空间复杂度O(1)，只使用常数额外空间

相关题目