Leetcode 838. 推多米诺 题解

题目链接：https://leetcode-cn.com/problems/push-dominoes/


O(n)遍历两趟算受力，代码如下：

class Solution {
public:
    string pushDominoes(string dominoes) {
        int len = dominoes.size();
        int left[100005] = {0};
        int right[100005] = {0};

        int force = 0;
        for(int i = 0; i < len; i++) {
            if(dominoes[i] == 'R') {
                force = len;
            } else if(dominoes[i] == 'L') {
                force = 0;
            } else {
                force = max(force - 1, 0);
            }
            left[i] = force;
        }

        force = 0;
        for(int i = len - 1; i >= 0; i--) {
            if(dominoes[i] == 'L') {
                force = len;
            } else if(dominoes[i] == 'R') {
                force = 0;
            } else {
                force = max(force - 1, 0);
            }
            right[i] = force;
        }

        for(int i = 0; i < len; i++) {
            cout << left[i] << " ";
        }
        cout << endl;
        for(int i = 0; i < len; i++) {
            cout << right[i] << " ";
        }

        char s[len + 1];
        string res = "";
        for(int i = 0; i < len; i++) {
            if(left[i] == right[i]) {
                s[i] = '.';
            } else if(left[i] > right[i]) {
                s[i] = 'R';
            } else {
                s[i] = 'L';
            }
        }
        s[len] = '\0';
        return s;
    }
};