[LeetCode] 每日一题 2711. 对角线上不同值的数量差（灵活使用前后缀思维化简）

题目链接

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

解题思路

这道题的核心在于计算每个位置的左上对角线和右下对角线上的不同值的数量。最初我想到的方案是直接模拟计算每个单元格的topLeft和bottomRight，但是这种方法复杂度较高，达到 O(m n min(m, n))，因为我们需要在每个单元格中遍历其所在对角线

随后我意识到对角线有一个规律：同一条对角线的元素的 i - j 值是相同的，因此我们可以按对角线来遍历矩阵，这样可以避免重复计算。我们令 k = i - j + n，这样每条对角线的元素都可以通过 k 来区分。然后，我们通过按对角线编号来遍历整个矩阵，对于每条对角线的元素，我们先计算左上对角线的不同值，再计算右下对角线的不同值，最终得到所需的答案

通过这种方法，我们将计算的复杂度降低到了 O(m * n)，避免了重复计算，效率更高

代码实现

class Solution {
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] ans = new int[m][n];
        HashSet<Integer> set = new HashSet<>();
        for (int k = 1; k <= m + n - 1; k++) {
            int jMin = Math.max(n - k, 0);
            int jMax = Math.min(m + n - 1 - k, n - 1);
            for (int j = jMin; j <= jMax; j++) {
                int i = k + j - n;
                ans[i][j] = set.size();
                set.add(grid[i][j]);
            }
            set.clear();
            for (int j = jMax; j >= jMin; j--) {
                int i = k + j - n;
                ans[i][j] = Math.abs(ans[i][j] - set.size());
                set.add(grid[i][j]);
            }
            set.clear();
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(m n)，我们遍历整个矩阵，并且在每个元素所在的对角线中计算不同值的数量，遍历一次矩阵可以获得最终结果。因此，时间复杂度为 O(m n)

• 空间复杂度：O(m n)，我们使用了一个 HashSet 来存储当前对角线上的不同值，这需要 O(m n) 的空间。由于我们没有使用额外的二维数组来存储其他状态，因此空间复杂度是 O(m * n)

总结

这道题通过巧妙地利用对角线的规律，避免了重复计算。通过按对角线遍历矩阵，我们可以分别计算每个单元格的topLeft和bottomRight值，并高效地求解出最终答案。初步的思路可能会使用双重遍历，但通过转化为对角线遍历，优化了时间复杂度和空间复杂度💡

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。