目标

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出：0

说明：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 10^4
• 0 <= threshold <= 10^5

思路

有一个 m x n 矩阵，返回其中元素和不超过 threshold 的正方形的最大边长。

使用二维前缀和计算面积，枚举右下顶点与边长，边长从已知的最大值开始枚举，超出 threshold 就退出循环，时间复杂度为 O(mn + min(m, n))。

代码

/**
 * @date 2026-01-19 9:46
 */
public class MaxSideLength1292 {

    public int maxSideLength_v1(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i][j - 1] + mat[i - 1][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
                int l = Math.min(i, j);
                for (int k = res + 1; k <= l; k++) {
                    int area = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];
                    if (area <= threshold) {
                        res = Math.max(res, k);
                    } else {
                        break;
                    }
                }
            }
        }
        return res;
    }

}

性能

目标

一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

示例 1：

输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12

示例 2：

输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
输出：2

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 10^6

思路

找出 m x n 矩阵中的最大幻方的边长。

暴力枚举顶点与边长，判断是否是幻方。可以记录水平、垂直、主对角线和副对角线上的前缀和，方便幻方判断。另外边长可以从大到小枚举，是幻方就直接返回。

代码

/**
 * @date 2026-01-19 14:59
 */
public class LargestMagicSquare1895 {

    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int l = Math.min(i, j) + 1;
                for (int k = res + 1; k <= l; k++) {
                    if (isMagicSquare(grid, i, j, k)) {
                        res = k;
                    }
                }
            }
        }
        return res;
    }

    public boolean isMagicSquare(int[][] grid, int x, int y, int l) {
        int diagonal1 = 0;
        int diagonal2 = 0;
        for (int k = 0; k < l; k++) {
            diagonal1 += grid[x - k][y - k];
            diagonal2 += grid[x - l + 1 + k][y - k];
        }
        if (diagonal1 != diagonal2) {
            return false;
        }

        for (int i = x - l + 1; i <= x; i++) {
            int sum = 0;
            for (int j = y - l + 1; j <= y; j++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        for (int j = y - l + 1; j <= y; j++) {
            int sum = 0;
            for (int i = x - l + 1; i <= x; i++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：

• 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -1 。

如果两个元素有 公共边 ，那么它们就是 相邻 的。

你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。

示例 1：

输入：matrix = [[1,-1],[-1,1]]
输出：4
解释：我们可以执行以下操作使和等于 4 ：
- 将第一行的 2 个元素乘以 -1 。
- 将第一列的 2 个元素乘以 -1 。

示例 2：

输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
输出：16
解释：我们可以执行以下操作使和等于 16 ：
- 将第二行的最后 2 个元素乘以 -1 。

说明：

• n == matrix.length == matrix[i].length
• 2 <= n <= 250
• -10^5 <= matrix[i][j] <= 10^5

思路

有一个 n x n 矩阵，每次操作可以将相邻的元素乘以 -1，执行操作任意次，求能够得到的最大方阵和。

经过观察发现，可以将任意两个元素乘以 -1，只需对路径上的每个元素执行操作，改变 (cur, next) 的符号，中间每个元素的符号都被改变了两次，即首尾元素改变了符号。

只需判断矩阵中负数的个数，如果是偶数，可以将负数全部变为相反数；如果是奇数，则需要找到最小的非负数，将其变为负数，其余元素全部变为非负数。

代码

/**
 * @date 2026-01-05 9:07
 */
public class MaxMatrixSum1975 {

    public long maxMatrixSum(int[][] matrix) {
        long res = 0L;
        int negativeCnt = 0;
        int min = Integer.MAX_VALUE;
        for (int[] row : matrix) {
            for (int col : row) {
                res += Math.abs(col);
                min = Math.min(min, Math.abs(col));
                if (col < 0) {
                    negativeCnt++;
                }
            }
        }
        if (negativeCnt % 2 == 1) {
            res -= 2 * min;
        }
        return res;
    }

}

性能

目标

3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

示例 1：

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]

输出: 1

解释:

下面的子矩阵是一个 3 x 3 的幻方：

而这一个不是：

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]]
输出: 0

说明:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

思路

判断给定矩阵中幻方的数量，幻方是一个九宫格，元素为 1 ~ 9 且行/列/对角线的元素和相等。

如果数字是 1 ~ 9，所有元素和为 45，幻方和为 sum / 3 = 15。将过中心的四条线相加，刚好等于 sum + 3 * center = 4 * 15 = 60，求得 center = 5。

使用 mask 记录出现过的数字，全部出现的二进制表示为 1111111110，即 2^10 - 1 - 1。

在保证数字是 1 ~ 9 的前提下，如果判断了前两行满足条件，则无需判断最后一行，同理，如果判断了前两列满足条件，无需判断最后一列。因为总和是 45，剩余的行/列和等于 45 - 30 = 15。在此基础上，对角线也无需判断，由于中间元素是 5，对角和一定是 10。

a b c
d e f
g h i

由于行/列和为 15，那么 b + h = d + f = 10。1 ~ 9 范围内和为 10 的组合只有四种 1 9，2 8，3 7，4 6。剩余四个位置 a c g i，如果对角和不等于 10，有 a + c 或 a + g 等于 10，但是 b 与 d 不可能为 5，矛盾。而如果 a i 和为 10，剩余的 c g 和也为 10。

代码

/**
 * @date 2025-12-30 9:10
 */
public class NumMagicSquaresInside840 {

    public int numMagicSquaresInside(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (m < 3 || n < 3) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (check(grid, i, j)) {
                    res++;
                }
            }
        }
        return res;
    }

    public boolean check(int[][] grid, int i, int j) {
        if (grid[i][j] != 5) {
            return false;
        }
        int[] rowSum = new int[3];
        int[] colSum = new int[3];
        int mask = 0;
        int r = 0;
        for (int row = i - 1; row <= i + 1; row++) {
            int c = 0;
            for (int col = j - 1; col <= j + 1; col++) {
                rowSum[r] += grid[row][col];
                colSum[c++] += grid[row][col];
                mask |= 1 << grid[row][col];
            }
            r++;
        }
        return rowSum[0] == 15 && rowSum[1] == 15 && colSum[0] == 15 && colSum[1] == 15 && mask == (1 << 10) - 2;
    }

}

性能

目标

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

思路

依题意模拟即可。

代码

/**
 * @date 2025-01-19 20:00
 */
public class IsValidSudoku36 {

    public boolean isValidSudoku(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            boolean[] exists = new boolean[10];
            for (int j = 0; j < n; j++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                if (exists[c - '0']) {
                    return false;
                }
                exists[c - '0'] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            boolean[] exists = new boolean[10];
            for (int i = 0; i < m; i++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                if (exists[c - '0']) {
                    return false;
                }
                exists[c - '0'] = true;
            }
        }
        boolean[] exists = null;
        for (int j = 0; j < n; j += 3) {
            for (int i = 0; i < m; i++) {
                if (i % 3 == 0) {
                    exists = new boolean[10];
                }
                for (int k = j; k < j + 3; k++) {
                    char c = board[i][k];
                    if ('.' == c) {
                        continue;
                    }
                    if (exists[c - '0']) {
                        return false;
                    }
                    exists[c - '0'] = true;
                }
            }
        }
        return true;
    }

}

性能

目标

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

• 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
• 右上角三角形 的对角线按 非递减顺序 排序。

示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]
输出： [[8,2,3],[9,6,7],[4,5,1]]
解释：
标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：
[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：
[7, 2] 变为 [2, 7]。
[3] 保持不变。

示例 2：

输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解释：
标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]
输出： [[1]]
解释：
只有一个元素的对角线已经符合要求，因此无需修改。

说明：

• grid.length == grid[i].length == n
• 1 <= n <= 10
• -10^5 <= grid[i][j] <= 10^5

思路

参考 498.对角线遍历

代码

/**
 * @date 2025-08-28 8:57
 */
public class SortMatrix3446 {

    public int[][] sortMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int k = m + n - 1;
        for (int l = 1; l < n; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(null);
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        for (int l = n; l <= k; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(Collections.reverseOrder());
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        return grid;
    }
}

性能

目标

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1：

输入： grid = [[0,1,0],[1,0,1]]
输出： 6
解释：
这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]
输出： 1
解释：
这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

说明：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 是 0 或 1。
• 输入保证 grid 中至少有一个 1 。

思路

已知一个二维 二进制数组，找出包含矩阵中所有 1 的矩阵的最小面积。

找到 1 的横纵坐标的上下界即可。

代码

/**
 * @date 2025-08-22 10:08
 */
public class MinimumArea3195 {

    public int minimumArea(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int rowMin = m - 1, rowMax = 0;
        int colMin = n - 1, colMax = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowMin = Math.min(rowMin, i);
                    rowMax = Math.max(rowMax, i);
                    colMin = Math.min(colMin, j);
                    colMax = Math.max(colMax, j);
                }
            }
        }
        return (rowMax - rowMin + 1) * (colMax - colMin + 1);
    }

}

性能

目标

给你一个下标从 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

思路

计算矩阵元素左上对角线的不同元素个数与右下对角线的不同元素个数的差的绝对值。即将元素所在的左上右下对角线，以当前元素为分界点（不包括当前元素），分成左上与右下两部分，计算每部分不同元素的个数，取差的绝对值。

暴力解法是枚举每个格子的左上右下元素，每一对角线都要遍历它所包含的元素个数次。

可以直接按对角线遍历，先记录前缀中的不同元素个数，然后再倒着遍历，计算差值的绝对值。

网友提到由于元素值不大，可以将其保存到 long 型数字中。

代码

/**
 * @date 2025-03-25 0:12
 */
public class DifferenceOfDistinctValues2711 {

    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m + n - 1; i++) {
            int row = i / n < 1 ? 0 : i - n + 1 % m;
            int col = row > 0 ? 0 : n - 1 - i;
            Set<Integer> set = new HashSet<>();
            while (row < m && col < n){
                res[row][col] = set.size();
                set.add(grid[row][col]);
                row++;
                col++;
            }
            row--;
            col--;
            set.clear();
            while (row >= 0 && col >= 0){
                res[row][col] = Math.abs(res[row][col] - set.size());
                set.add(grid[row][col]);
                row--;
                col--;
            }
        }
        return res;
    }

}

性能