1727. Largest Submatrix With Rearrangements

📘 題目敘述

給你一個大小為 m x n 的二元矩陣 matrix，你可以任意重新排列矩陣的欄。

請回傳在最佳欄位重排之後，所有元素都是 1 的最大子矩陣面積。

條件限制

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10^5
matrix[i][j] 只會是 0 或 1

🧠 解題思路

這題的重點不是直接去想怎麼交換欄，而是先想：

如果我固定看某一列當作子矩陣的最底部，那我能往上延伸多高？

所以我先做一個 ones 矩陣，ones[i][j] 表示：

在位置 (i, j) 這格，如果它是 1
那它往上連續有幾個 1

例如某一欄如果長這樣：

那對應的連續高度就會是：

有了這個高度之後，每一列就可以想成：

這一列有哪些欄，能提供多高的「1 的柱子」

而題目允許重新排列欄，所以對某一列來說，我可以把高的柱子排在一起。既然如此，對每一列我只要把高度由大到小排序，然後試：

取前 1 個欄時，面積是多少
取前 2 個欄時，面積是多少
...
取前 k 個欄時，面積是多少

如果排序後某列是：

[4, 3, 3, 1]

那：

取前 1 個欄，面積是 4 * 1
取前 2 個欄，面積是 3 * 2
取前 3 個欄，面積是 3 * 3
取前 4 個欄，面積是 1 * 4

因為當你取前 k 個欄時，真正能形成矩形的高度，會被第 k 高那根柱子限制住。

所以這題的核心就是：

先把每格往上連續的 1 高度算出來
對每一列把這些高度排序
枚舉這一列拿幾個欄一起組矩形，更新最大面積

也就是說，這題真正不是在模擬欄怎麼換，而是：

對每一列，把它當成矩形底邊，算出這一列各欄能提供的高度，再利用排序模擬最佳欄位重排。

所有變數

ones：ones[i][j] 表示位置 (i, j) 往上連續有幾個 1
ans：目前找到的最大子矩陣面積
row：在掃 ones 時，代表其中一列高度資料

🪜 主要流程步驟

1. 先開一個 ones 矩陣，記錄每格往上連續 1 的高度

int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> ones(m, vector<int>(n));

這裡先把矩陣大小存起來，並建立一個同大小的 ones。

之後 ones[i][j] 不是單純記 0 或 1，而是要記：

這格當作底部時，往上連續有幾個 1

2. 逐格建立 ones，高度由上往下累積

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (i == 0) {
            ones[i][j] = matrix[i][j];
            continue;
        }
        if (matrix[i][j] == 1) {
            ones[i][j] = ones[i - 1][j] + 1;
        } else {
            ones[i][j] = 0;
        }
    }
}

這一步是在建立每格的高度資訊。

先看第一列：

如果 i == 0
那往上沒有別的列了
所以 ones[0][j] 就直接等於 matrix[0][j]

也就是：

如果這格是 1，高度就是 1
如果這格是 0，高度就是 0

接著看其他列：

如果 matrix[i][j] == 1
- 代表這格可以接在上面那格的連續 1 下面
- 所以高度是 ones[i - 1][j] + 1
如果 matrix[i][j] == 0
- 代表這格不能形成連續 1
- 高度直接歸零

做完這一步後，ones 裡每一格就都變成「以這格為底，往上有多高」。

3. 對每一列排序，模擬把高的欄位排在一起

int ans = 0;
for (auto& row : ones) {
    sort(row.begin(), row.end(), greater<int>());

因為題目允許重新排列整個欄，所以對某一列來說，只要知道每個欄位的高度就夠了。

而要形成最大面積的矩形，直覺上就會希望：

高的欄位排在前面
這樣取前幾個欄時，最矮的那根也盡量高

所以這裡把每一列的高度由大到小排序。

這其實就是在模擬：

如果我可以任意重排欄位
那這一列最好的排列方式就是讓高的柱子集中在一起

4. 枚舉這一列取前幾個欄，計算可能的矩形面積

    for (int l = 0; l < n; l++) {
        ans = max(ans, row[l] * (l + 1));
    }
}

這一段是整題最核心的面積計算。

假設某列排序後長這樣：

row = [5, 4, 4, 2]

那代表：

如果只取前 1 個欄，矩形高度是 5，寬度是 1
如果取前 2 個欄，矩形高度會被第 2 根柱子限制成 4，寬度是 2
如果取前 3 個欄，高度還是 4，寬度是 3
如果取前 4 個欄，高度變成 2，寬度是 4

所以每次取前 l + 1 個欄時：

高度就是 row[l]
寬度就是 l + 1

因此面積就是：

row[l] * (l + 1)

把所有列、所有可能寬度都試過一遍，更新最大值即可。

5. 為什麼這樣就等於最佳重排後的答案

題目允許你重排欄位，但不能改變每一欄上下原本的結構。

而 ones[i][j] 已經完整描述了：

如果第 j 欄在第 i 列當底，最多可以提供多高的連續 1

所以對每一列來說，真正重要的不是欄原本順序，而是：

這列有哪些高度可以用

一旦把高度排序，就等於在模擬最佳欄位重排。接著再試每個可能的寬度，就能得到以這一列為底時的最大面積。

最後對所有列取最大值，就是整體答案。

6. 最後回傳 ans

return ans;

當所有列都處理完後，ans 就是最佳欄位重排後，全 1 子矩陣的最大面積。

⏱️ 複雜度

設 m = matrix.length，n = matrix[0].length。

時間複雜度：O(mn log n) 建立 ones 需要 O(mn)，之後每一列排序需要 O(n log n)，共 m 列。
空間複雜度：O(mn) 額外使用了一個 ones 矩陣來記錄每格的高度。

💻 程式碼實作

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> ones(m, vector<int>(n));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    ones[i][j] = matrix[i][j];
                    continue;
                }
                if (matrix[i][j] == 1) {
                    ones[i][j] = ones[i - 1][j] + 1;
                } else {
                    ones[i][j] = 0;
                }
            }
        }

        int ans = 0;
        for (auto& row : ones) {
            sort(row.begin(), row.end(), greater<int>());
            for (int l = 0; l < n; l++) {
                ans = max(ans, row[l] * (l + 1));
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/largest-submatrix-with-rearrangements/