矩阵 – 第 2 页 – shelterofly

目标

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中向右或向下移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有最大非负积的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回最大非负积对 10^9 + 7 取余的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。

示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)

示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

说明：

m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

思路

有一个矩阵 grid，从左上角 (0, 0) 出发向右或向下移动到达 (m - 1, n - 1)。路径的乘积指路径经过的所有元素乘积，返回最大的非负乘积。

由于存在负值，总的最大非负路径可能由最小值与当前值相乘得到。

定义 dp[i][j][0] 表示到达 (i, j) 的最大路径积，dp[i][j][1] 表示到达 (i, j) 的最小路径积。状态转移方程为：

dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘
dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘

代码


/**
 * @date 2026-03-23 9:12
 */
public class MaxProductPath1594 {

    public int maxProductPath(int[][] grid) {
        int mod = 1000000007;
        int m = grid.length;
        int n = grid[0].length;
        long[][][] dp = new long[m][n][2];
        dp[0][0][0] = grid[0][0];
        dp[0][0][1] = grid[0][0];
        for (int j = 1; j < n; j++) {
            dp[0][j][0] = dp[0][j - 1][0] * grid[0][j];
            dp[0][j][1] = dp[0][j - 1][1] * grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
            dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
                dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
            }
        }
        return dp[m - 1][n - 1][0] < 0 ? -1 : (int) (dp[m - 1][n - 1][0] % mod);
    }

}

性能

目标

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现以 90 度顺时针轮转矩阵 mat 中的元素若干次，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

示例 1：

输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。

示例 2：

输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。

示例 3：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。

说明：

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] 和 target[i][j] 不是 0 就是 1

思路

两个 n x n 矩阵 mat 与 target，判断能否通过若干次顺时针旋转 90° 使得 mat 与 target 相等。

参考 48.旋转图像直接原地旋转 mat 比较两个矩阵是否相等，最多旋转 4 次。

代码


/**
 * @date 2026-04-16 17:10
 */
public class FindRotation1886 {

    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length;
        here:
        for (int i = 0; i < 4; i++) {
            rotate(mat);
            for (int a = 0; a < n; a++) {
                for (int b = 0; b < n; b++) {
                    if (mat[a][b] != target[a][b]) {
                        continue here;
                    }
                }
            }
            return true;
        }
        return false;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

}

性能

目标

给你一个 m x n 的整数矩阵 grid，以及三个整数 x、y 和 k。

整数 x 和 y 表示一个正方形子矩阵的左上角下标，整数 k 表示该正方形子矩阵的边长。

你的任务是垂直翻转子矩阵的行顺序。

返回更新后的矩阵。

示例 1：

输入： grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], x = 1, y = 0, k = 3
输出： [[1,2,3,4],[13,14,15,8],[9,10,11,12],[5,6,7,16]]
解释：
上图展示了矩阵在变换前后的样子。

示例 2：

输入： grid = [[3,4,2,3],[2,3,4,2]], x = 0, y = 2, k = 2
输出： [[3,4,4,2],[2,3,2,3]]
解释：
上图展示了矩阵在变换前后的样子。

说明：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 100
0 <= x < m
0 <= y < n
1 <= k <= min(m - x, n - y)

思路

将矩阵 grid 的正方形子矩阵 (x, y, k) 上下翻转，(x, y) 表示子矩阵的左上顶点，k为子矩阵边长。

根据题意交换正方形子矩阵的上下对称的行即可。

代码


/**
 * @date 2026-04-17 11:11
 */
public class ReverseSubmatrix3643 {

    public int[][] reverseSubmatrix(int[][] grid, int x, int y, int k) {
        int l = k / 2;
        for (int i = 0; i < l; i++) {
            for (int j = y; j < y + k; j++) {
                int tmp = grid[x + i][j];
                grid[x + i][j] = grid[x + k - i - 1][j];
                grid[x + k - i - 1][j] = tmp;
            }
        }
        return grid;
    }
}

性能

目标

给你一个 m x n 的整数矩阵 grid 和一个整数 k。

对于矩阵 grid 中的每个连续的 k x k 子矩阵，计算其中任意两个不同值之间的最小绝对差。

返回一个大小为 (m - k + 1) x (n - k + 1) 的二维数组 ans，其中 ans[i][j] 表示以 grid 中坐标 (i, j) 为左上角的子矩阵的最小绝对差。

注意：如果子矩阵中的所有元素都相同，则答案为 0。

子矩阵 (x1, y1, x2, y2) 是一个由选择矩阵中所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的单元格 matrix[x][y] 组成的矩阵。

示例 1：

输入： grid = [[1,8],[3,-2]], k = 2
输出： [[2]]
解释：
只有一个可能的 k x k 子矩阵：[[1, 8], [3, -2]]。
子矩阵中的不同值为 [1, 8, 3, -2]。
子矩阵中的最小绝对差为 |1 - 3| = 2。因此，答案为 [[2]]。

示例 2：

输入： grid = [[3,-1]], k = 1
输出： [[0,0]]
解释：
每个 k x k 子矩阵中只有一个不同的元素。
因此，答案为 [[0, 0]]。

示例 3：

输入： grid = [[1,-2,3],[2,3,5]], k = 2
输出： [[1,2]]
解释：
    有两个可能的 k × k 子矩阵：
        以 (0, 0) 为起点的子矩阵：[[1, -2], [2, 3]]。
            子矩阵中的不同值为 [1, -2, 2, 3]。
            子矩阵中的最小绝对差为 |1 - 2| = 1。
        以 (0, 1) 为起点的子矩阵：[[-2, 3], [3, 5]]。
            子矩阵中的不同值为 [-2, 3, 5]。
            子矩阵中的最小绝对差为 |3 - 5| = 2。
    因此，答案为 [[1, 2]]。

说明：

1 <= m == grid.length <= 30
1 <= n == grid[i].length <= 30
-10^5 <= grid[i][j] <= 10^5
1 <= k <= min(m, n)

思路

有一个 m x n 矩阵 grid，返回所有 k x k 子矩阵的最小绝对差，最小绝对差指矩阵中任意两个元素相减的差的绝对值。k x k 子矩阵以左上角为标识，将结果保存到二维矩阵中。

最小的绝对差一定在大小相邻的元素中产生，可以暴力枚举，使用有序集合保存子矩阵中的元素，然后遍历有序集合，记录相邻元素的绝对差取最小的即可。

代码


/**
 * @date 2026-03-20 11:11
 */
public class MinAbsDiff3567 {

    public int[][] minAbsDiff(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m - k + 1][n - k + 1];
        for (int[] row : res) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        for (int i = 0; i < m - k + 1; i++) {
            for (int j = 0; j < n - k + 1; j++) {
                TreeSet<Integer> set = new TreeSet<>();
                for (int x = i; x < i + k; x++) {
                    for (int y = j; y < j + k; y++) {
                        set.add(grid[x][y]);
                    }
                }
                if (set.size() <= 1) {
                    res[i][j] = 0;
                    continue;
                }
                Iterator<Integer> iterator = set.iterator();
                int prev = iterator.next();
                while (iterator.hasNext()) {
                    Integer cur = iterator.next();
                    res[i][j] = Math.min(res[i][j], Math.abs(cur - prev));
                    prev = cur;
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：

包含 grid[0][0]
'X' 和 'Y' 的频数相等。
至少包含一个 'X'。

示例 1：

输入： grid = [["X","Y","."],["Y",".","."]]
输出： 3

示例 2：

输入： grid = [["X","X"],["X","Y"]]
输出： 0
解释：
不存在满足 'X' 和 'Y' 频数相等的子矩阵。

示例 3：

输入： grid = [[".","."],[".","."]]
输出： 0
解释：
不存在满足至少包含一个 'X' 的子矩阵。

说明：

1 <= grid.length, grid[i].length <= 1000
grid[i][j] 可能是 'X'、'Y' 或 '.'.

思路

有一个矩阵 grid，其元素为 X Y .，求满足条件的子矩阵数量。要求子矩阵包含左上角 grid[0][0]，并且至少包含一个 X，且 X 与 Y 的数量相等。

二维前缀和。

代码


/**
 * @date 2026-03-19 8:49
 */
public class NumberOfSubmatrices3212 {

    public int numberOfSubmatrices(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] xCnt = new int[m + 1][n + 1];
        int[][] yCnt = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                xCnt[i + 1][j + 1] = xCnt[i][j + 1] + xCnt[i + 1][j] - xCnt[i][j];
                yCnt[i + 1][j + 1] = yCnt[i][j + 1] + yCnt[i + 1][j] - yCnt[i][j];
                if (grid[i][j] == 'X') {
                    xCnt[i + 1][j + 1]++;
                } else if (grid[i][j] == 'Y') {
                    yCnt[i + 1][j + 1]++;
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (xCnt[i][j] == yCnt[i][j] && xCnt[i][j] != 0) {
                    res++;
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的子矩阵的数目。

示例 1：

输入：grid = [[7,6,3],[6,6,1]], k = 18
输出：4
解释：如上图所示，只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。

示例 2：

输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20
输出：6
解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

提示：

m == grid.length
n == grid[i].length
1 <= n, m <= 1000
0 <= grid[i][j] <= 1000
1 <= k <= 10^9

思路

有一个矩阵 grid，求包含左上角 grid[0][0] 的子矩阵中，元素和小于等于 k 的子矩阵数量。

二维前缀和。

代码


/**
 * @date 2026-03-18 8:47
 */
public class CountSubmatrices3070 {

    public int countSubmatrices(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + grid[i][j];
                if (prefix[i + 1][j + 1] <= k) {
                    res++;
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的列按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。

示例 1：

输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。

示例 2：

输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。

示例 3：

输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。

示例 4：

输入：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。

说明：

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10^5
matrix[i][j] 要么是 0 ，要么是 1 。

提示：

For each column, find the number of consecutive ones ending at each position.
For each row, sort the cumulative ones in non-increasing order and "fit" the largest submatrix.

思路

有一个 m x n 二进制矩阵 matrix，可以重新排列矩阵的列，求全 1 子矩阵的最大面积。

如果不允许重新排列，统计全1子矩阵的个数，参考 1504.统计全1子矩形枚举底边与右边界。

针对每一列记录以当前行为终点连续 1 的高度，然后按高度排序，那么以当前行为底的最大子矩阵就可以求出来了。

代码


/**
 * @date 2026-03-17 9:37
 */
public class LargestSubmatrix1727 {

    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] ones = new int[m][n];
        System.arraycopy(matrix[0], 0, ones[0], 0, n);
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    ones[i][j] = ones[i - 1][j] + 1;
                }
            }
        }
        int res = 0;
        for (int[] row : ones) {
            Arrays.sort(row);
            int i = n - 1;
            int l = 1;
            int max = 0;
            while (i >= 0 && row[i] > 0) {
                max = Math.max(max, row[i--] * l++);
            }
            res = Math.max(res, max);
        }
        return res;
    }
}

性能

目标

给你一个 m x n 的整数矩阵 grid 。

菱形和指的是 grid 中一个正菱形边界上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。

注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。

请你按照降序返回 grid 中三个最大的互不相同的菱形和。如果不同的和少于三个，则将它们全部返回。

示例 1：

输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
输出：[228,216,211]
解释：最大的三个菱形和如上图所示。
- 蓝色：20 + 3 + 200 + 5 = 228
- 红色：200 + 2 + 10 + 4 = 216
- 绿色：5 + 200 + 4 + 2 = 211

示例 2：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
- 蓝色：4 + 2 + 6 + 8 = 20
- 红色：9 （右下角红色的面积为 0 的菱形）
- 绿色：8 （下方中央面积为 0 的菱形）

示例 3：

输入：grid = [[7,7,7]]
输出：[7]
解释：所有三个可能的菱形和都相同，所以返回 [7] 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 10^5

思路

有一个 m x n 矩阵 grid，返回矩阵中最大的三个 不相同 的菱形和。满足条件的菱形指矩阵内部的正方形顺时针旋转 45°，并且四个角必须占一个格子的正方形。菱形和就是其边界上的元素之和。

枚举所有合法的正菱形。针对每一个元素 (i, j)，枚举以它作为对角线交点的所有可能的正菱形（正方形）。

经过观察发现，如果边上元素个数为 k + 1，那么上顶点坐标为 (i - k, j)，下顶点坐标为 (i + k, j)，左顶点坐标为 (i, j - k)，右顶点坐标为 (i, j + k)。

枚举 (i, j) 所在行 [j - k, j + k] 范围内的元素。注意左右顶点的上下元素重合到自身，不能重复累加。特殊处理两端点，中间枚举 x ∈ [j - k + 1, j + k - 1] 累加上下 h 的元素值，即 (i - h, x) 与 (i + h, x)。其中 h = k - Math.abs(j - x)，k 表示中点到四个角的距离，x 表示列标，j - x 表示列标距离中点的距离。

上面的解法针对每一个中点重复累加了边上的元素和。更好做法是使用两个二维数组分别表示两个方向 ↘ ↙ 上截止到 (u, v) 的前缀和。中点确定之后，可以确定边的四个角，进而可以计算前缀和。注意不要重复计算四个角。

代码


/**
 * @date 2026-03-16 9:37
 */
public class GetBiggestThree1878 {

    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; i + k < m && i - k >= 0 && j - k >= 0 && j + k < n; k++) {
                    int sum = 0;
                    if (k == 0) {
                        set.add(grid[i][j]);
                        continue;
                    }
                    sum += grid[i][j - k] + grid[i][j + k];
                    for (int x = j - k + 1; x <= j + k - 1; x++) {
                        int h = k - Math.abs(j - x);
                        sum += grid[i - h][x] + grid[i + h][x];
                    }
                    set.add(sum);
                }
            }
        }
        int size = Math.min(3, set.size());
        int[] res = new int[size];
        Iterator<Integer> iterator = set.iterator();
        for (int i = 0; i < size; i++) {
            res[i] = iterator.next();
        }
        return res;
    }

}

性能

1582.二进制矩阵中的特殊位置

目标

给定一个 m x n 的二进制矩阵 mat，返回矩阵 mat 中特殊位置的数量。

如果位置 (i, j) 满足 mat[i][j] == 1 并且行 i 与列 j 中的所有其他元素都是 0（行和列的下标从 0 开始计数），那么它被称为特殊位置。

示例 1：

输入：mat = [[1,0,0],[0,0,1],[1,0,0]]
输出：1
解释：位置 (1, 2) 是一个特殊位置，因为 mat[1][2] == 1 且第 1 行和第 2 列的其他所有元素都是 0。

示例 2：

输入：mat = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：位置 (0, 0)，(1, 1) 和 (2, 2) 都是特殊位置。

说明：

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] 是 0 或 1。

思路

返回二进制矩阵 mat 的特殊位置个数，所谓特殊位置指，当前位置的值为 1，且所在行列的其它元素均为 0。

计算每行每列中 1 的个数，如果当前单元格的值为 1，且行列 1 的个数也是 1，累加结果。

代码


/**
 * @date 2026-03-04 9:50
 */
public class NumSpecial1582 {

    public int numSpecial(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] rc = new int[m];
        int[] cc = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rc[i] += mat[i][j];
                cc[j] += mat[i][j];
            }
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            if (rc[i] > 1) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (cc[j] == 1 && mat[i][j] == 1) {
                    res++;
                }
            }
        }
        return res;
    }
}

性能

1536.排布二进制网格的最少交换次数

目标

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的相邻两行进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

示例 1：

输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

示例 2：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,1]]
输出：0

说明：

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] 要么是 0 要么是 1 。

提示：

For each row of the grid calculate the most right 1 in the grid in the array maxRight.
To check if there exist answer, sort maxRight and check if maxRight[i] ≤ i for all possible i's.
If there exist an answer, simulate the swaps.

思路

有一个 n x n 的二进制矩阵，每次操作可以交换相邻的两行，求使得矩阵主对角线之上的所有格子变为 0 所需的最小操作次数。

第 i 行最右侧的 1 的下标不能超过 i，如果不满足条件，找到第一个满足条件的行进行交换。这种贪心策略之所以可行，是因为如果存在多个满足条件的行，由于行从上到下的条件越来越宽松，满足当前行的条件也必定满足后续行，因此选最近的行交换即可。

代码


/**
 * @date 2026-03-02 8:45
 */
public class MinSwaps1536 {

    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] maxRight = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    maxRight[i] = j;
                    break;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (maxRight[i] <= i) {
                continue;
            }
            boolean flag = false;
            int prev = maxRight[i];
            for (int j = i + 1; j < n; j++) {
                if (maxRight[j] <= i) {
                    res += j - i;
                    flag = true;
                    maxRight[j] = prev;
                    break;
                }
                int tmp = maxRight[j];
                maxRight[j] = prev;
                prev = tmp;
            }
            if (!flag) {
                return -1;
            }
        }
        return res;
    }

}

2026 年 5 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31