# 1184. Distance Between Bus Stops

A bus has `n` stops numbered from `0` to `n - 1` that form a circle. We know the distance between all pairs of neighboring stops where `distance[i]` is the distance between the stops number `i` and `(i + 1) % n`.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given `start` and `destination` stops.

Example 1:

``````Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.
``````

Example 2:

``````Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.
``````

Example 3:

``````Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.
``````

Constraints:

• `1 <= n <= 10^4`
• `distance.length == n`
• `0 <= start, destination < n`
• `0 <= distance[i] <= 10^4`

``````class Solution {
public:
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
int total = accumulate(distance.begin(), distance.end(), 0), cur = 0, mx = max(start, destination);
for (int i = min(start, destination); i < mx; ++i) {
cur += distance[i];
}
return min(cur, total - cur);
}
};
``````

``````class Solution {
public:
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
int sum1 = 0, sum2 = 0, n = distance.size();
if (start > destination) swap(start, destination);
for (int i = 0; i < n; ++i) {
if (i >= start && i < destination) {
sum1 += distance[i];
} else {
sum2 += distance[i];
}
}
return min(sum1, sum2);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1184

https://leetcode.com/problems/distance-between-bus-stops/

https://leetcode.com/problems/distance-between-bus-stops/discuss/377568/C%2B%2B-one-pass

https://leetcode.com/problems/distance-between-bus-stops/discuss/377444/Java-O(n)-solution-Easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation