目标
给你一个 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;
}
}
性能
