📘 題目敘述
給你一個 m x n 的整數矩陣 grid，以及一個整數 k。
對於 grid 中每一個連續的 k x k 子矩陣，請計算這個子矩陣內任意兩個不同值之間的最小絕對差。
請回傳一個二維陣列 ans，大小為 (m - k + 1) x (n - k + 1)，其中 ans[i][j] 表示左上角在 (i, j) 的那個 k x k 子矩陣中的最小絕對差。
注意：如果該子矩陣中所有元素都相同，答案為 0。
子矩陣 (x1, y1, x2, y2) 表示所有滿足 x1 <= x <= x2 且 y1 <= y <= y2 的 matrix[x][y] 所組成的矩形區域。
條件限制
1 <= m == grid.length <= 301 <= n == grid[i].length <= 30-10^5 <= grid[i][j] <= 10^51 <= k <= min(m, n)
🧠 解題思路
我這份寫法是很直接的暴力做法：
對每一個 k x k 子矩陣，都把裡面的元素全部抓出來，排序後去找相鄰不同數字之間的最小差值。
這題有一個很重要的觀察：
如果一堆數字排好序後，最小絕對差一定只會出現在相鄰的不同元素之間。
所以我不需要去枚舉子矩陣裡所有兩兩配對，那樣會很亂。
只要把子矩陣內的值收集到一個陣列 v 裡，排序之後掃一遍：
- 如果
v[k] == v[k + 1] -
- 代表有重複值
- 這對不同位置雖然值一樣，但題目要的是不同值，所以這種不算差值候選
- 如果
v[k] != v[k + 1] -
- 那就計算
v[k + 1] - v[k] - 並維護最小值
- 那就計算
而如果整個子矩陣裡所有值都相同，那排序後就永遠不會出現 v[k] != v[k + 1] 的情況，
這時我這份程式的 d 會一直保持 0，剛好符合題目要求。
整體流程就是：
- 枚舉每個可能的
k x k子矩陣左上角(i, j) - 呼叫
givemin(grid, i, j)去算這塊子矩陣的答案 givemin裡把子矩陣的數字抓出來、排序、掃相鄰差值- 把結果填進
ans[i][j]
也就是說，這題的核心就是：
對每個
k x k子矩陣，把所有值取出後排序，再從排序後的相鄰不同元素中找最小差值。
所有變數
s：目前子矩陣的邊長，也就是輸入的kv：存某個k x k子矩陣裡所有元素的一維陣列d：目前這個子矩陣中找到的最小絕對差m：矩陣列數n：矩陣行數ans：答案矩陣
🪜 主要流程步驟
1. 先把子矩陣邊長 k 存到成員變數 s
s = k;這樣後面的 givemin 就不用每次再多傳一個邊長進去，
它只要知道目前左上角在哪裡，就能直接抓出一個 s x s 的子矩陣。
2. 建立答案矩陣 ans
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> ans(m - k + 1, vector<int>(n - k + 1));因為一個 m x n 的矩陣中，左上角能放 k x k 子矩陣的位置共有：
- 列方向：
m - k + 1 - 行方向：
n - k + 1
所以答案矩陣大小就是：
(m - k + 1) x (n - k + 1)
3. 枚舉每個 k x k 子矩陣的左上角
for (int i = 0; i <= m - k; i++) {
for (int j = 0; j <= n - k; j++) {
ans[i][j] = givemin(grid, i, j);
}
}這裡的 (i, j) 就代表某個 k x k 子矩陣的左上角。
每個位置都呼叫一次 givemin(grid, i, j)，把那塊子矩陣的最小絕對差算出來，填進答案矩陣。
4. 在 givemin 裡，把這個子矩陣所有元素抓出來
vector<int> v;
for (int i = l; i < l + s; i++) {
for (int j = r; j < r + s; j++) {
v.push_back(grid[i][j]);
}
}這一步是在把左上角為 (l, r)、大小為 s x s 的整塊子矩陣展平成一個一維陣列 v。
因為後面我要排序，所以先全部抓出來最直接。
如果 k = 2，那就是把這 2 x 2 區塊的四個值全部塞進 v。
5. 對子矩陣內的所有值排序
sort(v.begin(), v.end());這一步很重要。
因為排序後，最小絕對差只需要在相鄰元素之間檢查就夠了。
不用去枚舉所有兩兩組合。
例如如果排序後是：
[-2, 1, 2, 3]
那最小差值只可能出現在：
1 - (-2)2 - 13 - 2
這些相鄰位置之間。
6. 掃排序後的相鄰元素，找最小的不同值差距
int d = 0;
for (int k = 0; k < v.size() - 1; k++) {
if (v[k] != v[k + 1]) {
if (d == 0) {
d = v[k + 1] - v[k];
}
d = min(d, v[k + 1] - v[k]);
}
}這段是 givemin 的核心。
這裡只處理：
v[k] != v[k + 1]
因為題目要求的是兩個不同值之間的最小絕對差。
如果兩個值一樣，那不算候選。
d 一開始設成 0，表示目前還沒找到任何一組不同值。
當第一次遇到不同值時，就先把那個差距存進去。
之後每遇到新的不同值差距，就用 min 更新。
7. 如果整塊子矩陣所有值都相同，答案自然會維持 0
這份程式裡：
int d = 0;如果排序後整個 v 都是同一個值，那 v[k] != v[k + 1] 永遠不成立，
所以 d 不會被更新，最後直接回傳 0。
這剛好符合題目規定：
- 如果所有元素都相同，答案就是
0
8. 回傳這個子矩陣的最小絕對差
return d;givemin 算完後，把這塊子矩陣的答案回傳給 minAbsDiff，再填進對應位置的 ans[i][j]。
9. 最後回傳整個答案矩陣
return ans;當所有 k x k 子矩陣都處理完後，ans 就是題目要的結果。
⏱️ 複雜度
設 m = grid.length，n = grid[0].length。
- 時間複雜度：
O((m - k + 1)(n - k + 1) · k^2 log(k^2))
一共有(m - k + 1)(n - k + 1)個子矩陣，每個子矩陣要取出k^2個元素並排序。 - 空間複雜度：
O(k^2)givemin中額外使用了一個大小為k^2的陣列v來存子矩陣元素。
💻 程式碼實作
class Solution {
public:
int s;
int givemin(vector<vector<int>>& grid, int l, int r) {
vector<int> v;
for (int i = l; i < l + s; i++) {
for (int j = r; j < r + s; j++) {
v.push_back(grid[i][j]);
}
}
sort(v.begin(), v.end());
int d = 0;
for (int k = 0; k < v.size() - 1; k++) {
if (v[k] != v[k + 1]) {
if (d == 0) {
d = v[k + 1] - v[k];
}
d = min(d, v[k + 1] - v[k]);
}
}
return d;
}
vector<vector<int>> minAbsDiff(vector<vector<int>>& grid, int k) {
s = k;
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> ans(m - k + 1, vector<int>(n - k + 1));
for (int i = 0; i <= m - k; i++) {
for (int j = 0; j <= n - k; j++) {
ans[i][j] = givemin(grid, i, j);
}
}
return ans;
}
};🔗 題目連結
https://leetcode.com/problems/minimum-absolute-difference-in-sliding-submatrix/