如何用JavaScript统计车辆经过测速摄像头的次数？

给定代表道路的字符串S，各字符含义如下：

"<" -> 向左行驶的车辆
">" -> 向右行驶的车辆
"." -> 测速摄像头

需统计车辆经过测速摄像头的总次数，规则为：向右行驶的车辆仅经过其右侧的摄像头，向左行驶的车辆仅经过其左侧的摄像头。

要求编写函数：

function solution(S);

该函数接收长度为N的字符串S，返回车辆经过摄像头的总次数。

示例：

给定S = ".>..."，函数应返回3。
给定S = ".>.<.>"，函数应返回4。
给定S = ">>>.<<<"，函数应返回6。

双指针法容易在数据量较大时超时，本质是最坏情况下时间复杂度会达到O(n²)。换用线性遍历的思路可以彻底解决超时问题：

• 正向遍历：维护一个计数器记录当前位置左侧所有向右行驶的车辆数。每遇到测速摄像头（.），就把当前计数器的值加到总次数里——这些向右的车辆都会经过这个位于它们右侧的摄像头。
• 反向遍历：维护另一个计数器记录当前位置右侧所有向左行驶的车辆数。每遇到测速摄像头（.），就把当前计数器的值加到总次数里——这些向左的车辆都会经过这个位于它们左侧的摄像头。

两次遍历都是线性时间，仅需几个变量存储计数，空间复杂度为O(1)，完全不会出现超时。

JavaScript 实现代码 #

function solution(S) {
    let total = 0;
    let rightCars = 0;

    // 正向统计向右车辆经过右侧摄像头的次数
    for (const c of S) {
        if (c === '>') {
            rightCars++;
        } else if (c === '.') {
            total += rightCars;
        }
    }

    let leftCars = 0;
    // 反向统计向左车辆经过左侧摄像头的次数
    for (let i = S.length - 1; i >= 0; i--) {
        const c = S[i];
        if (c === '<') {
            leftCars++;
        } else if (c === '.') {
            total += leftCars;
        }
    }

    return total;
}

示例验证 #

• 对于 S = ".>..."：正向遍历中，3个右侧摄像头各被1辆向右车辆经过，贡献3次；反向无向左车辆，总次数为3。
• 对于 S = ".>.<.>"：正向贡献2次，反向贡献2次，总和4。
• 对于 S = ">>>.<<<"：正向3辆向右车辆经过中间摄像头，贡献3次；反向3辆向左车辆经过中间摄像头，贡献3次，总和6。

内容的提问来源于stack exchange，提问作者FePaiva