2211. 統計道路上的碰撞次數

思路

要滿足相撞的條件有三種。

1. R L，左邊往右，右邊往左，碰撞次數 + 2。
2. R S，左邊往右，右邊不動，碰撞次數 + 1。
3. S L，左邊不動，右邊往左，碰撞次數 + 1。 碰撞過後留下一片碎渣，可以視為兩台車合體，在原地留下不動的一台車輛 S。
   而這台留下來的車可能會繼續跟左邊或是右邊的車相撞，因此需要多次判斷。

第二個想法，
根據條件，可以看出碰撞時，R S 有幾個，碰撞次數就加幾個。
一開始，去掉左側往左前進的車（最左連續的 L），以及右邊往右前進的車（最右連續的 R），
因為這些車不可能碰撞。
判斷之後，中段肯定會互相碰撞，算一算中間有幾個 R S, 即為所求。

程式碼

1. stack

class Solution {
public:
    int countCollisions(string directions) {
        // 需要一直往左撞
        string stk;
        int res = 0;
        for(char& dir : directions) {
            stk += dir;
            while(stk.size() >= 2) { // 每次取最上面兩個，判斷碰撞
                // 情況 1
                if(stk[stk.size() - 2] == 'R' && stk.back() == 'L') {
                    res += 2;
                    stk.pop_back();
                    stk.back() = 'S';
                }
                // 情況 2, 3
                else if(stk[stk.size() - 2] == 'R' && stk.back() == 'S' || 
                        stk[stk.size() - 2] == 'S' && stk.back() == 'L') { 
                    res++;
                    stk.pop_back();
                    stk.back() = 'S';
                }
                // 沒有碰撞
                else {
                    break;
                }
            }
        }
        return res;
    }
};

2. 計數

class Solution {
public:
    int countCollisions(string directions) {
        int n = directions.size();
        int left = 0, right = n;
        while(left < n && directions[left] == 'L') {
            ++left;
        }
        while(right > left && directions[right - 1] == 'R') {
            --right;
        } 
        int res = 0;
        for(int i = left; i < right; ++i) {
            res += directions[i] != 'S';
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：思路一$O(n)$，思路二$O(1)$