[数据结构与算法]leetcode2211.统计道路上的碰撞次数（中等，周赛）

自己的思路：直接模拟，不太好。。

方法一：这类题的常规解法->栈
具体细节：栈内存**‘R’或者’S’，从左向右遍历**

’L’且栈内有元素：不断出栈顶元素直到栈顶元素不是’R‘，出一次ans++（向右的车发生碰撞）；最后ans++（该车发生碰撞） 然后将’S’入栈。
’R’：stk.push(‘R’);
’S’：不断出栈顶元素直到栈顶元素不是’R‘，出一次ans++（向右的车发生碰撞）； 然后将’S’入栈。

class Solution {
public:
    int countCollisions(string directions) {

        stack<char> stk;
        int ans = 0;
        for (auto ch : directions) {
            if (ch == 'L' && stk.size()) {
                while (stk.size() && stk.top() == 'R') {
                    stk.pop();
                    ans++;
                }
                ans++;
                stk.push('S');
            }else if (ch == 'R') {
                stk.push('R');
            }else if (ch == 'S'){
                while (stk.size() && stk.top() == 'R') {
                    stk.pop();
                    ans++;
                }
                stk.push('S');
            }
        }
        return ans;
    }
};

方法二：脑筋急转弯
具体思路：最左边的L一定不会碰撞 最右边的也是，其余都会碰撞（除去S的车辆）

class Solution {
public:
    int countCollisions(string directions) {
 
        int ans = 0, n = directions.size();
        int i, j;
        for (i = 0; i < n && directions[i] == 'L'; ++i) ans++;
        for (j = n - 1; j >= 0 && directions[j] == 'R'; --j) ans++;
        for (int k = i; k <= j; ++k) {
            if (directions[k] == 'S') n--;
        }
        return n - ans;
    }
};