难度: Hard
Submission
运行时间: 244 ms
内存: 33.4 MB
class Solution:
def minScore(self, grid: List[List[int]]) -> List[List[int]]:
m, n = len(grid), len(grid[0])
positions = sorted(((r, c) for r in range(m) for c in range(n)), key=lambda t: grid[t[0]][t[1]])
rMax, cMax = [0]*m, [0]*n
for r, c in positions:
val = max(rMax[r], cMax[c]) + 1
rMax[r] = cMax[c] = val
grid[r][c] = val
return grid
Explain
此题解的思路是首先将网格中的所有位置按照其中的值进行排序。接着，按照排序后的顺序（从小到大），为每个位置计算一个新的值。新值是该位置所在行和列中当前最大值加一，这样可以确保这个位置的值是目前为止在它的行和列中最大的。这种处理保证了较小的原始值对应的新值也较小，从而尽量减小网格中的最大值。
时间复杂度: O(m*n log(m*n))
空间复杂度: O(m*n)
class Solution:
def minScore(self, grid: List[List[int]]) -> List[List[int]]:
m, n = len(grid), len(grid[0])
# 创建一个位置列表，并按照网格中的值排序
positions = sorted(((r, c) for r in range(m) for c in range(n)), key=lambda t: grid[t[0]][t[1]])
# 初始化记录每行和每列的最大值的数组
rMax, cMax = [0]*m, [0]*n
# 遍历每个位置，更新网格值和行列最大值
for r, c in positions:
val = max(rMax[r], cMax[c]) + 1 # 计算新值
rMax[r] = cMax[c] = val # 更新行和列的最大值
grid[r][c] = val # 更新网格位置
return grid
Explore
在算法中，将网格中的所有位置按照其中的值进行排序是为了确保处理顺序从最小值开始到最大值结束。这种排序方式有助于逐步构建每个位置的新值，同时尽可能保持这个新值小。因为较小的值先被处理，其对应的新值也会较小，而后处理的较大的值，其新值基于已经较高的行或列最大值进行更新，从而使得整个网格中的最大值尽可能小。因此，排序确实有助于减小网格中的最大值。
计算新值的方式 `max(rMax[r], cMax[c]) + 1` 确实能保证这个新值是行和列中的当前最大值，因为它基于当前行和列中已记录的最大值进行计算，并且加一确保新值大于任何已存在的值。不存在特殊情况使得这个假设失效，因为每次更新值都是基于最大值，并且递增确保了新值总是最大的。
在这个算法中同时设置 `rMax[r]` 和 `cMax[c]` 为相同的值 `val` 是因为此时在位置 `(r, c)` 更新了网格的值为 `val`，这个值是基于行和列当前的最大值计算得出的。这样做确保了在任何后续操作中，这个行或列的最大值都是准确的。因为每个位置更新时都考虑了其所在行和列的最大值，所以不会导致记录不准确。
在网格只有一行或一列的情况下，算法的基本逻辑保持不变。即使只有一行，每个元素仍按照原始值排序并更新，使用行最大值进行计算。类似地，如果只有一列，仍按照排序更新每个元素，使用列最大值进行计算。这种情况下算法的行为与多行多列的情况相似，唯一的区别是不需要考虑其他行或列的最大值，因为只有一行或一列。