📘 題目敘述
給你一個 n x n 的二元矩陣 grid，一次操作中你可以選擇 grid 的兩個相鄰列（rows）並交換它們。
如果一個矩陣滿足：主對角線（main diagonal）上方的所有格子都是 0，則稱這個矩陣是 valid。
請回傳把 grid 變成 valid 所需的最少操作次數；如果不可能變成 valid，回傳 -1。
主對角線是從格子 (1, 1) 到 (n, n) 的那條對角線。
條件限制
n == grid.length == grid[i].length1 <= n <= 200grid[i][j]只會是0或1
🧠 解題思路
這題的條件「主對角線上方全是 0」可以換成每一列的限制來看：
第 i 列（0-index）在對角線上方的位置是 j > i。所以第 i 列必須滿足：在 j = i+1 到 n-1 這段都要是 0。
換句話說：
第
i列的尾端至少要有n - i - 1個連續的 0。
所以我先把每一列尾端連續 0 的數量算出來，存成一個陣列 v。
接著從上到下依序安排每一列：
- 第
i列需要v[j] >= n - i - 1 - 我在剩下的列裡從上往下找第一個符合的列（最靠前的）
- 找到後把它「搬到」目前位置，搬動需要的相鄰交換次數就是它距離目前位置的步數
- 我用
ans += j來累積這個搬動成本（因為我直接把那一列從v刪掉，等於把它提到最前面） - 如果找不到任何列符合，就代表不可能，回傳
-1
這就是一個典型的 greedy：每一層都選「最靠前」能滿足需求的列，因為這樣交換次數最少。
所有變數
n：矩陣大小（列數 / 行數）。v：v[r]代表第r列尾端連續 0 的數量。ans：累積的最少相鄰列交換次數。count：在計算某一列尾端 0 時的計數器。check：用來判斷第i個位置是否找得到可用的列（找不到就回傳 -1）。
🪜 主要流程步驟
1. 先把每一列「尾端連續 0 的數量」算出來放進 v
我對每一列從最右邊開始往左掃：
- 只要遇到 0 就
count++ - 一旦遇到 1 就停止
最後把 count 放進 v。這一步完成後，v 就代表每列的「可用程度」。
2. 從上到下依序決定第 i 列要放哪一列
對於位置 i，它需要的尾端 0 數量是：need = n - i - 1
我在目前剩下的 v 裡從前往後找第一個 v[j] >= need 的列。
3. 找到就把它搬上來，ans 加上搬動距離，並從 v 移除
假設我找到的是第 j 個：
把它搬到目前的位置需要做 j 次相鄰交換（往上推 j 格）。
所以我做：
ans += jv.erase(v.begin() + j)
這個 erase 的效果等於把那列抽出來放到前面（已經固定到第 i 列），剩下的列相對順序不變。
4. 如果某個 i 找不到任何符合的列，就回傳 -1
如果整個 v 掃完都沒有 v[j] >= need，代表無論怎麼交換都無法讓第 i 列達成條件，直接回傳 -1。
5. 全部位置都安排完成後回傳 ans
如果 i = 0..n-1 都能找到列，代表一定能組成 valid grid，回傳累積的 ans。
⏱️ 複雜度
- 時間複雜度：
O(n^2)。先算v是O(n^2)（每列最多掃 n 次），後面安排每一列也可能掃v，再加上erase的位移成本，整體在n <= 200下可接受。 - 空間複雜度：
O(n)，主要是v陣列。
💻 程式碼實作
class Solution {
public:
int minSwaps(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> v;
for (auto& row : grid) {
int count = 0;
for (int j = n - 1; j >= 0; j--) {
if (row[j] == 0) {
count++;
} else {
break;
}
}
v.push_back(count);
}
int ans = 0;
for (int i = 0; i < n; i++) {
bool check = true;
for (int j = 0; j < v.size(); j++) {
if (v[j] >= n - i - 1) {
check = false;
ans += j;
v.erase(v.begin() + j);
break;
}
}
if (check) {
return -1;
}
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid/