Medium

题目描述

一些机器人站在一个无限数轴上，它们的初始坐标由一个 0 索引的整数数组 nums 给出，一旦接到移动命令，它们就开始移动。机器人每秒移动一个单位距离。

给你一个字符串 s，表示机器人接到命令后移动的方向。'L' 表示机器人将向左侧或数轴的负方向移动，而 'R' 表示机器人将向右侧或数轴的正方向移动。

如果两个机器人相撞，它们将开始朝相反的方向移动。

返回指令发出 d 秒后，所有机器人之间两两距离的总和。由于总和可能很大，请返回对 10^9 + 7 取余的结果。

注意：

  • 对于索引 i 和 j 处的两个机器人，配对 (i,j) 和配对 (j,i) 被认为是同一配对。
  • 当机器人相撞时，它们会立即改变方向而不浪费任何时间。
  • 当两个机器人在某一时刻位于同一位置时就发生碰撞。

示例 1：

输入：nums = [-2,0,2], s = "RLL", d = 3
输出：8
解释：
1秒后，位置为 [-1,-1,1]。现在索引0的机器人向左移动，索引1的机器人向右移动。
2秒后，位置为 [-2,0,0]。现在索引1的机器人向左移动，索引2的机器人向右移动。
3秒后，位置为 [-3,-1,1]。
索引0和1之间的距离为 abs(-3 - (-1)) = 2。
索引0和2之间的距离为 abs(-3 - 1) = 4。
索引1和2之间的距离为 abs(-1 - 1) = 2。
所有配对距离的总和 = 2 + 4 + 2 = 8。

示例 2：

输入：nums = [1,0], s = "RL", d = 2
输出：5
解释：
1秒后，位置为 [2,-1]。
2秒后，位置为 [3,-2]。
两个机器人之间的距离为 abs(-2 - 3) = 5。

约束条件：

  • 2 <= nums.length <= 10^5
  • -2 * 10^9 <= nums[i] <= 2 * 10^9
  • 0 <= d <= 10^9
  • nums.length == s.length
  • s 仅由 ‘L’ 和 ‘R’ 组成
  • nums[i] 是唯一的

解题思路

这道题的关键观察是：虽然机器人会碰撞并改变方向，但忽略碰撞的情况下，d秒后所有机器人的位置集合是相同的。

核心思路

碰撞只是改变了机器人的标识，但不影响最终位置的分布。我们可以这样理解：

  • 每个机器人按初始方向移动d秒，得到一组位置
  • 将这些位置排序后，就是d秒后实际的机器人位置

具体步骤：

  1. 计算理想位置：根据每个机器人的初始位置和方向，计算忽略碰撞时d秒后的位置
  2. 排序位置：将所有位置按升序排列
  3. 计算距离和：使用前缀和优化计算所有两两距离的总和

距离和计算优化

对于排序后的位置数组，计算所有配对距离：

  • 对于位置 pos[i]，它与前面所有位置的距离和为：i * pos[i] - prefixSum[i-1]
  • 使用前缀和避免重复计算

这种方法将时间复杂度从 O(n²) 优化到 O(n log n)。

代码实现

class Solution {
public:
    int sumDistance(vector<int>& nums, string s, int d) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        vector<long long> positions;
        
        // 计算忽略碰撞时d秒后的位置
        for (int i = 0; i < n; i++) {
            if (s[i] == 'L') {
                positions.push_back((long long)nums[i] - d);
            } else {
                positions.push_back((long long)nums[i] + d);
            }
        }
        
        // 排序位置
        sort(positions.begin(), positions.end());
        
        // 使用前缀和计算距离总和
        long long result = 0;
        long long prefixSum = 0;
        
        for (int i = 0; i < n; i++) {
            result = (result + (long long)i * positions[i] - prefixSum) % MOD;
            prefixSum = (prefixSum + positions[i]) % MOD;
        }
        
        return (result + MOD) % MOD;
    }
};

class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # 计算忽略碰撞时d秒后的位置
        positions = []
        for i in range(n):
            if s[i] == 'L':
                positions.append(nums[i] - d)
            else:
                positions.append(nums[i] + d)
        
        # 排序位置
        positions.sort()
        
        # 使用前缀和计算距离总和
        result = 0
        prefix_sum = 0
        
        for i in range(n):
            result = (result + i * positions[i] - prefix_sum) % MOD
            prefix_sum = (prefix_sum + positions[i]) % MOD
        
        return result

public class Solution {
    public int SumDistance(int[] nums, string s, int d) {
        const int MOD = 1000000007;
        int n = nums.Length;
        long[] positions = new long[n];
        
        // 计算忽略碰撞时d秒后的位置
        for (int i = 0; i < n; i++) {
            if (s[i] == 'L') {
                positions[i] = (long)nums[i] - d;
            } else {
                positions[i] = (long)nums[i] + d;
            }
        }
        
        // 排序位置
        Array.Sort(positions);
        
        // 使用前缀和计算距离总和
        long result = 0;
        long prefixSum = 0;
        
        for (int i = 0; i < n; i++) {
            result = (result + (long)i * positions[i] - prefixSum) % MOD;
            prefixSum = (prefixSum + positions[i]) % MOD;
        }
        
        return (int)((result + MOD) % MOD);
    }
}

var sumDistance = function(nums, s, d) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    const positions = [];
    
    // 计算忽略碰撞时d秒后的位置
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(n)
  • 时间复杂度：主要来自排序操作，为 O(n log n)
  • 空间复杂度：需要存储位置数组，为 O(n)

相关题目