1184. 公交站间的距离

🟢   🔖  数组  🔗 力扣 LeetCode

题目

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

题目大意

环形公交路线上有 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

解题思路

本题的关键在于计算从出发站 start 到目的地站 destination 之间的最短距离。由于是环形公交路线，乘客可以选择顺时针或逆时针的方向行驶。

1. 计算环形公交的总距离：
   通过 distance.reduce() 求得整个环线的总长度，表示顺时针方向的总距离。
2. 交换起点和终点： 如果 start > destination，则交换 start 和 destination，方便计算。
3. 计算顺时针方向的距离：
   顺时针距离为从 start 到 destination 的一段，按顺序累加 distance[i] 直到到达 destination。
4. 计算逆时针方向的距离：
   总环路的距离减去顺时针的距离即可得到逆时针的距离。
5. 返回最短距离：
   取顺时针和逆时针两者的较小值作为最终结果。

复杂度分析

• 时间复杂度：O(n)
  • 计算总环路的距离需要遍历 distance 数组一次，时间复杂度为 O(n)。
  • 计算顺时针的距离最多也是遍历一次 distance 数组，时间复杂度为 O(n)。
  • 总的时间复杂度为 O(n)。
• 空间复杂度：O(1)，我们只用了常数空间来存储一些辅助变量。

代码

/**
 * @param {number[]} distance
 * @param {number} start
 * @param {number} destination
 * @return {number}
 */
var distanceBetweenBusStops = function (distance, start, destination) {
	// 获取环形公交的总距离
	const total = distance.reduce((acc, cur) => acc + cur, 0);

	// 交换起点和终点
	if (start > destination) {
		let temp = start;
		start = destination;
		destination = temp;
	}

	// 计算顺时针方向的距离
	let sum = 0;
	for (let i = start; i < destination; i++) {
		sum += distance[i];
	}
	// 返回较小的距离
	return Math.min(sum, total - sum);
};

相关题目

题号	标题	题解	标签	难度	力扣
2361	乘坐火车路线的最少费用 🔒		数组 动态规划	🔴	🀄️ 🔗