难度: Medium
Submission
运行时间: 69 ms
内存: 16.1 MB
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
m,n,mark=len(board),len(board[0]),True
while mark:
mark=False #表示暂时没有可消除的相同数字。
for i in range(m):
for j in range(n):
if board[i][j]==0:
continue
#于每个非零元素，检查水平方向和垂直方向上是否存在连续三个相同的数字。如果存在，则将这三个数字的值都设置为它们的相反数。这一步是为了标记这些数字为待消除状态，并将 mark 设为 True，表示存在可消除的相同数字。
if j<n-2 and abs(board[i][j])==abs(board[i][j+1])==abs(board[i][j+2]):
val=-abs(board[i][j])
board[i][j]=val
board[i][j+1]=val
board[i][j+2]=val
mark=True
if i<m-2 and abs(board[i][j])==abs(board[i+1][j])==abs(board[i+2][j]):
mark=True
val=-abs(board[i][j])
board[i][j]=val
board[i+1][j]=val
board[i+2][j]=val
mark=True
#次遍历整个矩阵，对于每一列，将非零元素移动到当前列的最底部。这是通过维护一个指针 cursor 来实现的。首先将 cursor 初始化为当前列的最底部，然后从底向上遍历当前列，如果遇到非零元素，则将其移动到 cursor 所指的位置，并将 cursor 向上移动一位。剩余的空位填充0。
for j in range(n):
cursor=m-1
for i in range(m-1,-1,-1):
if board[i][j]>0:
board[cursor][j]=board[i][j]
cursor-=1
for i in range(cursor,-1,-1):
board[i][j]=0
return board
Explain
这个题解采用了两次遍历的方法来解决粉碎糖果问题。第一次遍历中，对每个非零元素，检查其水平和垂直方向上是否存在连续三个相同的数字。如果存在，则将这些数字标记为待消除状态（取相反数）。第二次遍历中，对每一列进行处理，将非零元素移动到当前列的底部，其余位置填充为0。重复这个过程，直到不存在可消除的相同数字为止。
时间复杂度: O(m^2 * n^2)
空间复杂度: O(1)
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
m, n, mark = len(board), len(board[0]), True
while mark:
mark = False # 表示暂时没有可消除的相同数字
for i in range(m):
for j in range(n):
if board[i][j] == 0:
continue
# 检查水平方向上是否存在连续三个相同的数字
if j < n - 2 and abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]):
val = -abs(board[i][j])
board[i][j] = val
board[i][j + 1] = val
board[i][j + 2] = val
mark = True
# 检查垂直方向上是否存在连续三个相同的数字
if i < m - 2 and abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]):
mark = True
val = -abs(board[i][j])
board[i][j] = val
board[i + 1][j] = val
board[i + 2][j] = val
mark = True
# 将非零元素移动到当前列的底部，剩余空位填充0
for j in range(n):
cursor = m - 1
for i in range(m - 1, -1, -1):
if board[i][j] > 0:
board[cursor][j] = board[i][j]
cursor -= 1
for i in range(cursor, -1, -1):
board[i][j] = 0
return board
Explore
在算法中，通过使用数字的绝对值来进行连续性检查，可以确保标记待消除状态的数字不会影响其他连续三个数字的判断。即便数字被标记为负值（待消除状态），其绝对值仍然保持不变，因此在检查时使用绝对值abs可以正确地识别连续的相同数字，避免了标记影响判断的问题。
使用取相反数的方法来标记待消除的数字的主要优点是节省空间和简化操作。这种方法不需要额外的存储空间来记录状态（如布尔数组所需的额外空间），同时也避免了使用特殊值可能带来的数值冲突问题（特殊值可能与有效数据冲突）。通过简单地取负值，可以在不改变原有数组结构的基础上，有效地标记和识别待消除的数字。
在列元素移动的处理中，算法确保只有大于0的元素（有效数字）才被向下移动。由于待消除的数字被标记为负值，这些数字在移动过程中不会被视为有效数字。因此，在向下移动过程中，不会误将已标记为待消除的数字（负值）当作有效数字处理。这种区分通过检查数字是否大于0来实现。
在处理边界条件时，算法通过限制索引范围来确保不会越界。例如，在检查水平连续三个相同数字时，会确保索引j小于n-2，这样在j, j+1, j+2访问时不会超过矩阵的右边界。同样地，检查垂直连续三个相同数字时，会确保索引i小于m-2，以避免在i, i+1, i+2访问时超过矩阵的下边界。这样的索引限制确保了即使是在矩阵的边缘也不会出现越界错误。