Medium

题目描述

在一条无限长的道路上有 n 辆车。这些车从左到右按 0 到 n-1 编号，每辆车都在一个独特的位置上。

给你一个长度为 n 的下标从 0 开始的字符串 directions，其中 directions[i] 可以是 ‘L’、‘R’ 或 ‘S’，表示第 i 辆车是向左移动、向右移动还是停在当前位置。每辆移动的车都有相同的速度。

碰撞次数的计算方式如下：

  • 当两辆向相反方向移动的车相撞时，碰撞次数增加 2。
  • 当一辆移动的车与一辆静止的车相撞时，碰撞次数增加 1。

碰撞后，涉及的车辆将无法继续移动，并停留在碰撞点。除此之外，车辆无法改变其状态或运动方向。

返回道路上将发生的碰撞总数。

示例 1：

输入：directions = "RLRSLL"
输出：5
解释：
道路上将发生的碰撞有：
- 车 0 和车 1 将相互碰撞。由于它们向相反方向移动，碰撞次数变为 0 + 2 = 2。
- 车 2 和车 3 将相互碰撞。由于车 3 是静止的，碰撞次数变为 2 + 1 = 3。
- 车 3 和车 4 将相互碰撞。由于车 3 是静止的，碰撞次数变为 3 + 1 = 4。
- 车 4 和车 5 将相互碰撞。车 4 与车 3 碰撞后，将停留在碰撞点并被车 5 撞击。碰撞次数变为 4 + 1 = 5。
因此，道路上将发生的碰撞总数是 5。

示例 2：

输入：directions = "LLRR"
输出：0
解释：
没有车会相互碰撞。因此，道路上将发生的碰撞总数是 0。

提示：

  • 1 <= directions.length <= 10^5
  • directions[i] 是 ‘L’、‘R’ 或 ‘S’ 中的一个

解题思路

这道题的关键是理解什么时候车辆不会发生碰撞。

核心观察：

  1. 最左边连续的 ‘L’ 车辆永远不会发生碰撞（它们向左移动，离开道路）
  2. 最右边连续的 ‘R’ 车辆永远不会发生碰撞（它们向右移动，离开道路）
  3. 中间部分的所有移动车辆（‘L’ 和 ‘R’）最终都会因为碰撞而停止

解题思路：

方法一：栈模拟（推荐） 使用栈模拟碰撞过程。遍历字符串，对于每个车辆：

  • ‘R’：直接入栈
  • ‘S’：检查栈顶是否为 ‘R’，如果是则发生碰撞，累加碰撞数并将栈顶改为 ‘S’
  • ‘L’：持续与栈顶的 ‘R’ 和 ‘S’ 碰撞，直到栈空或栈顶为 ‘L’

方法二：数学计算 直接计算：去掉最左边的连续 ‘L’ 和最右边的连续 ‘R’，中间所有的 ‘L’ 和 ‘R’ 都会发生碰撞，每个贡献 1 次碰撞。

两种方法时间复杂度相同，栈模拟更直观，数学计算更简洁。

代码实现

class Solution {
public:
    int countCollisions(string directions) {
        stack<char> st;
        int collisions = 0;
        
        for (char dir : directions) {
            if (dir == 'R') {
                st.push(dir);
            } else if (dir == 'S') {
                if (!st.empty() && st.top() == 'R') {
                    collisions++;
                    st.pop();
                }
                st.push('S');
            } else { // dir == 'L'
                while (!st.empty() && (st.top() == 'R' || st.top() == 'S')) {
                    if (st.top() == 'R') {
                        collisions += 2;
                    } else {
                        collisions++;
                    }
                    st.pop();
                }
                st.push('S');
            }
        }
        
        return collisions;
    }
};

class Solution:
    def countCollisions(self, directions: str) -> int:
        stack = []
        collisions = 0
        
        for direction in directions:
            if direction == 'R':
                stack.append(direction)
            elif direction == 'S':
                if stack and stack[-1] == 'R':
                    collisions += 1
                    stack.pop()
                stack.append('S')
            else:  # direction == 'L'
                while stack and (stack[-1] == 'R' or stack[-1] == 'S'):
                    if stack[-1] == 'R':
                        collisions += 2
                    else:
                        collisions += 1
                    stack.pop()
                stack.append('S')
        
        return collisions

public class Solution {
    public int CountCollisions(string directions) {
        Stack<char> stack = new Stack<char>();
        int collisions = 0;
        
        foreach (char dir in directions) {
            if (dir == 'R') {
                stack.Push(dir);
            } else if (dir == 'S') {
                if (stack.Count > 0 && stack.Peek() == 'R') {
                    collisions++;
                    stack.Pop();
                }
                stack.Push('S');
            } else { // dir == 'L'
                while (stack.Count > 0 && (stack.Peek() == 'R' || stack.Peek() == 'S')) {
                    if (stack.Peek() == 'R') {
                        collisions += 2;
                    } else {
                        collisions++;
                    }
                    stack.Pop();
                }
                stack.Push('S');
            }
        }
        
        return collisions;
    }
}

var countCollisions = function(directions) {
    let collisions = 0;
    let n = directions.length;
    let cars = directions.split('');
    
    let changed = true;
    while (changed) {
        changed = false;
        for (let i = 0; i < n - 1; i++) {
            if (cars[i] === 'R' && cars[i + 1] === 'L') {
                collisions += 2;
                cars[i] = 'S';
                cars[i + 1] = 'S';
                changed = true;
            } else if (cars[i] === 'R' && cars[i + 1] === 'S') {
                collisions += 1;
                cars[i] = 'S';
                changed = true;
            } else if (cars[i] === 'S' && cars[i + 1] === 'L') {
                collisions += 1;
                cars[i + 1] = 'S';
                changed = true;
            }
        }
    }
    
    return collisions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串 directions 的长度。每个字符最多被压入栈一次和弹出栈一次，所以时间复杂度是线性的。栈的最大空间为 O(n)。

相关题目