2711.对角线上不同值的数量差

dp, hash table, https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。

矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：

令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。
令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。

然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。

返回矩阵 answer 。

矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。

如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。

示例 1：

输入：grid = [[1,2,3],[3,1,5],[3,2,1]]
输出：[[1,1,0],[1,0,1],[0,1,1]]
解释：第 1 个图表示最初的矩阵 grid 。 
第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。
第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。
第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。
- 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。
- 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。
- 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。
其他单元格的对应答案也可以按照这样的流程进行计算。

示例 2：

输入：grid = [[1]]
输出：[[0]]
解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n, grid[i][j] <= 50

下面是一个基于动态规划、利用哈希表（Python 中使用 set 集合）的解法，思路是分别从左上和右下方向动态维护对角线上之前出现过的不同数值集合，从而计算每个位置的答案：

python

from typing import List

class Solution:
    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        # 初始化两个 m x n 的矩阵，用于存储每个位置左上和右下对角线（不包含当前位置）不同数值集合
        topLeft = [[set() for _ in range(n)] for _ in range(m)]
        bottomRight = [[set() for _ in range(n)] for _ in range(m)]
        
        # 从左上到右下，计算每个位置的左上对角线集合
        for i in range(m):
            for j in range(n):
                if i > 0 and j > 0:
                    # 集合继承左上邻居的集合并加上左上邻居的值
                    topLeft[i][j] = topLeft[i-1][j-1].copy()
                    topLeft[i][j].add(grid[i-1][j-1])
                # 如果 i==0 或 j==0, 则没有左上邻居, 保持为空集合
        
        # 从右下到左上，计算每个位置的右下对角线集合
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i < m-1 and j < n-1:
                    bottomRight[i][j] = bottomRight[i+1][j+1].copy()
                    bottomRight[i][j].add(grid[i+1][j+1])
                # 边界条件：最后一行或最后一列没有右下邻居
        
        # 构造结果矩阵，计算每个位置的答案为两个集合大小的差的绝对值
        answer = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                answer[i][j] = abs(len(topLeft[i][j]) - len(bottomRight[i][j]))
        return answer

# 示例测试
if __name__ == "__main__":
    sol = Solution()
    grid1 = [[1,2,3],[3,1,5],[3,2,1]]
    print(sol.differenceOfDistinctValues(grid1))  # 输出 [[1,1,0],[1,0,1],[0,1,1]]
    
    grid2 = [[1]]
    print(sol.differenceOfDistinctValues(grid2))  # 输出 [[0]]

代码说明

动态规划状态转移：
- 对于每个单元格 (i, j)，其左上集合来自于其左上邻居 (i-1, j-1) 的集合，并加入 (i-1, j-1) 的数值（如果存在）。
- 同理，右下集合由其右下邻居 (i+1, j+1) 的集合构成，并加入 (i+1, j+1) 的数值（如果存在）。
答案计算：
- 最后，答案矩阵中每个单元格为两个集合大小的差的绝对值。

这种方法时间复杂度约为 O(m*n)（由于 m,n 较小，此方法足够高效），同时使用空间保存每个单元格的集合。

Q: 为什么copy()?

在代码中使用 copy() 是为了创建当前集合的副本，而不是直接引用同一个集合对象。这样做有以下几个原因：

独立性：如果直接赋值而不调用 copy()，多个位置将引用同一个集合对象。后续在某个位置对集合进行修改时，会影响所有引用了该集合的单元格，导致结果不正确。
避免副作用：每个单元格需要维护自己独立的“左上”或“右下”集合。如果不复制，就会因为共享同一个集合而混淆数据，影响最终计算答案时集合大小的准确性。

总之，copy() 确保每个位置都有自己的独立集合，从而正确地累积对角线上的不同值。

2711.对角线上不同值的数量差 ​

2711.对角线上不同值的数量差