LeetCode 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 00是矩形的高，则矩形最大面积是0 × 3 = 0 0\times 3=00×3=0
2. 假设矩形从第二列开始，2 22是矩形的高，则矩形最大面积是2 × 2 = 4 2\times 2=42×2=4
3. 假设矩形从第三列开始，3 33是矩形的高，则矩形最大面积是3 × 1 = 3 3\times 1=33×1=3

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

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

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

• 时间复杂度O ( n m log ⁡ n ) O(nm\log n)O(nmlogn)
• 空间复杂度O ( n ) O(n)O(n)

AC代码

C++

/* * @LastEditTime: 2026-03-17 22:00:41 */classSolution{public:intlargestSubmatrix(vector<vector<int>>&matrix){intn=matrix[0].size();vector<int>heights(n);intans=0;for(vector<int>&row:matrix){for(inti=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(inti=0;i<n;i++){ans=max(ans,ordered_heights[i]*(n-i));}}returnans;}};

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

千篇源码题解已开源