1727.重新排列后的最大子矩阵：枚举矩形底边是哪一行 + 排序

【LetMeFly】1727.重新排列后的最大子矩阵：枚举矩形底边是哪一行 + 排序

力扣题目链接：https://leetcode.cn/problems/largest-submatrix-with-rearrangements/

给你一个二进制矩阵 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 <= 105
• matrix[i][j] 要么是 0 ，要么是 1 。

解题方法：枚举矩形底边是哪一行 + 排序

对于样例1：

，假设最优的答案矩形的底在第三行，那么怎么计算以第三行为底的矩形中面积最大的那个呢？

很简单，看下每一列从第三行开始向上能延伸多少格：[2, 0, 3]；排个序：[0, 2, 3]。

1. 假设矩形从第一列开始，$0$是矩形的高，则矩形最大面积是$0\times 3=0$
2. 假设矩形从第二列开始，$2$是矩形的高，则矩形最大面积是$2\times 2=4$
3. 假设矩形从第三列开始，$3$是矩形的高，则矩形最大面积是$3\times 1=3$

也就是说矩形从第$i$列开始的话，由于后面列的高都不低于这一列，所以矩形的最大面积是从这一列的高度一直持续到最后一列，为$heights[i]\times (n-i)$，其中$n$是列数。

也就是说，如果固定了矩形底边是哪一行的话，如果我们知道每一列以这个底边向上的连续1个数$height$，就能对$heights$数组从小到大排个序，然后遍历一遍求出最大矩形面积了。

现在底边有很多行，我们一行一行地枚举并做上述运算，顺便在枚举下一行的时候借助上一行的heights结果计算出新的heights就好了。

• 时间复杂度$O(nm\log n)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-17 22:00:41
 */
class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int n = matrix[0].size();
        vector<int> heights(n);
        int ans = 0;
        for (vector<int>& row : matrix) {
            for (int i = 0; i < n; i++) {
                heights[i] = row[i] ? heights[i] + 1 : 0;
            }
            vector<int> ordered_heights = heights;
            sort(ordered_heights.begin(), ordered_heights.end());
            for (int i = 0; i < n; i++) {
                ans = max(ans, ordered_heights[i] * (n - i));
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源