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

🎯 问题描述

描述：
给你一个下标从 0 开始的 m x n 二维整数数组 grid。
你需要返回一个同样大小的矩阵 answer，其中 answer[i][j] 的值为：

| \text{topLeft}[i][j] - \text{bottomRight}[i][j] |

其中：

topLeft[i][j] 表示单元格 (i, j) 左上角对角线（即行下标和列下标都小于 i 和 j 的方向）上不同值的数量。
bottomRight[i][j] 表示单元格 (i, j) 右下角对角线（即行下标和列下标都大于 i 和 j 的方向）上不同值的数量。
如果对角线上没有元素，则数量为 0。

说明：

这是一个矩阵对角线遍历问题。
核心策略：
- 同一条主对角线（左上到右下）上的元素，其坐标差 i - j 是恒定的。
- 我们可以根据 i - j 的值将矩阵元素分组到不同的对角线上。
- 对于每一条对角线，我们需要计算每个位置左侧（左上）的不同值数量和右侧（右下）的不同值数量。
优化技巧：
- 两次遍历法：先沿对角线从左上往右下遍历，计算并暂存 topLeft 值；再沿同一条对角线从右下往左上遍历，计算 bottomRight 值，并直接计算最终差值。
- 空间复用：利用结果矩阵 ans 暂存中间状态（topLeft），避免开辟额外数组。
示例：
示例 1：

输入：grid = [[1,2,3],[3,1,2]]
输出：[[0,1,1],[1,0,1]]
解释：
以 (1,1) 为例：
- 左上角对角线元素：[1] (来自 (0,0))。不同值数量 topLeft = 1。
- 右下角对角线元素：[2] (来自 (1,2) 越界? 不，是 (1,1) 的右下，即无元素)。
- 实际上 (1,1) 的右下没有元素，所以 bottomRight = 0。
- 结果 |1 - 0| = 1。

以 (0,1) 为例：
- 左上角：无元素，topLeft = 0。
- 右下角：(1,2) 越界，无元素，bottomRight = 0。
- 结果 |0 - 0| = 0。
(注：具体示例需根据题目实际对角线定义核对，此处仅为逻辑演示)

💻 解题思路

思路1：对角线分组 + 双向集合计数

核心逻辑

对角线标识：
- 主对角线方向（左上到右下）的特征是 i - j = C（常数）。
- 代码中使用 k 作为枚举变量，通过 i = k + j - n 变换，实际上是在遍历所有可能的 i - j 值。
- k 的范围 1 到 m + n - 1 覆盖了所有可能的对角线。
确定边界：
- 对于每条对角线，计算其在矩阵内的有效列下标范围 [min_j, max_j]。
- min_j = max(0, n - k) 和 max_j = min(n - 1, m - 1 + n - k) 确保了 i 和 j 都不越界。
正向遍历（计算 topLeft）：
- 沿对角线从左上（j 小）到右下（j 大）。
- 使用集合 st 记录当前点之前遇到的不同值。
- ans[i][j] = len(st)：此时集合大小即为左上角不同值数量。
- st.add(grid[i][j])：将当前值加入集合，供下一个点使用。
反向遍历（计算 bottomRight 并得出结果）：
- 沿同一条对角线从右下（j 大）到左上（j 小）。
- 清空集合 st。
- 使用集合 st 记录当前点之后（右下方）遇到的不同值。
- ans[i][j] = abs(ans[i][j] - len(st))：
  - ans[i][j] 中存的是刚才计算的 topLeft。
  - len(st) 是当前的 bottomRight。
  - 直接计算差值并更新 ans[i][j]。
- st.add(grid[i][j])：将当前值加入集合，供下一个点（左上方的点）使用。

代码实现

class Solution:
    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        ans = [[0] * n for _ in range(m)]
        st = set()
        
        # 枚举所有对角线
        # k 的作用是将 i-j 的差值映射到正整数范围
        for k in range(1, m + n):
            # 1. 计算当前对角线的列下标范围
            # 确保 i 和 j 都在合法范围内
            min_j = max(0, n - k)
            max_j = min(n - 1, m - 1 + n - k)
            
            # 2. 正向遍历：计算 topLeft
            # 方向：左上 -> 右下
            st.clear()
            for j in range(min_j, max_j + 1):
                i = k + j - n
                # 此时 st 中存储的是 (i,j) 左上角对角线上的不同值
                ans[i][j] = len(st)
                # 将当前值加入，供下一个点使用
                st.add(grid[i][j])

            # 3. 逆向遍历：计算 bottomRight 并更新最终答案
            # 方向：右下 -> 左上
            st.clear()
            for j in range(max_j, min_j - 1, -1):
                i = k + j - n
                # 此时 st 中存储的是 (i,j) 右下角对角线上的不同值
                # ans[i][j] 中存的是 topLeft
                # 计算差值的绝对值
                ans[i][j] = abs(ans[i][j] - len(st))
                # 将当前值加入，供下一个点（左上方的点）使用
                st.add(grid[i][j])
                
        return ans

📊 性能分析

时间复杂度： $O(M \times N)$ $O (M \times N)$
- 我们遍历了矩阵中的每一条对角线。
- 每个元素被访问两次（一次正向，一次逆向）。
- 集合操作（添加、查询大小）的平均时间复杂度为 $O(1)$ 。
- 总时间复杂度与矩阵元素数量成线性关系。
空间复杂度： $O(\min(M, N))$ $O (min (M, N))$
- 结果矩阵 ans 占用 $O(M \times N)$ 。
- 集合 st 用于存储不同值，其最大大小受限于对角线的最大长度，即 $O(\min(M, N))$ 。
- 注：如果不计算结果矩阵的空间，额外空间复杂度仅为 $O(\min(M, N))$ 。

思考

为什么可以复用 ans 数组？
- 在正向遍历时，我们需要存储 topLeft 的值。
- 在逆向遍历时，我们需要 topLeft 和 bottomRight 来计算结果。
- 此时 topLeft 已经计算完毕且不再改变，而 bottomRight 是即时计算的。
- 因此，我们可以先用 ans 存 topLeft，然后在逆向遍历时直接覆盖为最终结果。这是一种非常节省空间的技巧。
坐标变换公式 i = k + j - n：
- 这个公式定义了当前枚举的对角线。
- 实际上，这对应于 i - j = k - n。
- 令 $C = k - n$ ，则 i - j = C。这正是主对角线方向（左上到右下）的特征方程。
- 通过改变 k，我们遍历了所有可能的 $C$ 值，从而覆盖了整个矩阵。
集合 st 的作用：
- 集合用于去重。
- 正向遍历时，st 保存了当前点之前（左上方）遇到的所有不同值。
- 逆向遍历时，st 保存了当前点之后（右下方）遇到的所有不同值。
边界计算：
- min_j 和 max_j 的计算确保了我们在遍历对角线时不会越界访问矩阵。
- 这是通过对 i 和 j 的范围限制推导出来的。