В ряду стоит N костяшка костяшки, и мы ставим каждую костяшку вертикально вертикально.

В начале мы одновременно толкаем несколько костяшек то влево, то вправо.

Каждую секунду каждая костяшка домино, падающая влево, толкает соседнюю костяшку слева.

Точно так же кости домино, падающие вправо, толкают соседние кости домино, стоящие справа.

Когда на вертикальную костяшку с обеих сторон падают костяшки домино, она остается неподвижной из-за баланса сил.

Для целей этого вопроса мы будем считать, что падающая костяшка костяшки не затрачивает дополнительной силы по сравнению с падающей или уже упавшей костяшкой.

Дана строка «S», представляющая начальное состояние. S[i] = 'L', если i-я костяшка сдвинута влево; S[i] = 'R', если i-я костяшка сдвинута вправо; S[i] = '.', если не сдвинута i-я костяшка костяшки.

Возвращает строку, представляющую конечное состояние.

Мыслительный процесс

Предположим, что есть костяшки домино, падающие вправо, и костяшки, падающие влево, равноудаленные от позиции с непадающей костяшкой i (назовем ее «D») (между ними тоже непадающие костяшки), D не упадет. Одна костяшка слева от D упадет вправо, а одна костяшка справа от D упадет слева.

Ясно, что относительное расстояние от текущего положения стоящего костяшка домино и соседних костяшек домино, которые должны упасть, будет определять конечное состояние текущего стоящего костяшка домино.

Как решить

Следовательно, в любой позиции, если костяшка стоит, мы будем сравнивать расстояние до ближайшей падающей костяшки слева или справа. Ближайшая падающая костяшка решит судьбу стоящей костяшки.

Мы можем использовать left and rightvariables, где left[i] and right[i] хранит расстояние до ближайших падающих костяшек домино. Будет угловой случай, когда для позиции нет падающих переменных влево или вправо. В этом случае переменные будут хранить ∞.

Заполнение переменных

Затем, когда мы пересекаем i, у нас есть три варианта заполнения переменных. Чтобы проиллюстрировать, для leftvariable:

A) Если left[i] == «L», установите left[i] = 0, так как ближайшая «L» находится в той же позиции для заполнения;

Б) Если left[i]== «.», установить left[i] = left[i-1] + 1; и

C) Если left[i] == «R», left[i] не ставить, т.е. он останется как ∞.

Примечание. Для шага B есть два крайних случая), потому что i может быть в нулевой позиции, а left[i-1] не определено. В этом случае не устанавливайте и оставьте left[i=0] равным ∞. Или, left[i-1] равно ∞, что означает отсутствие падения «L» слева, тогда снова оставьте left[i] равным ∞.

Я оставлю упражнение для заполнения права [i] читателю.

Спойлеры кода (на Python) — не прокручивайте, если вы все еще пытаетесь понять

import math
class Solution:
    """
    @param dominoes: a string
    @return: a string representing the final state
    """
    def pushDominoes(self, dominoes):
        length = len(dominoes)
        left = [math.inf for _ in range(length)]
        right = [math.inf for _ in range(length)]
        res =  []
        
        for i in range(length):
            
            li = length - i - 1
            
            if dominoes[li] == "L":
                left[li] = 0
            elif dominoes[li] == ".":
                if li != length-1:
                    if left[li+1] != math.inf: #DP portion
                        left[li] = left[li+1] + 1          
                        
            if dominoes[i] == "R":
                right[i] = 0
            elif dominoes[i] == ".":
                if i != 0:
                    if right[i-1] != math.inf: #DP portion
                        right[i] = right[i-1] + 1
                    
        for i in range(length):
            if right[i] < left[i]:
                res.append("R")
            elif right[i] > left[i]:
                res.append("L")
            else:
                res.append(".")
        return "".join(res)