A.每日一题：1727. 重新排列后的最大子矩阵

题目链接：1727. 重新排列后的最大子矩阵（中等）

算法原理：

此题是A.每日一题——85. 最大矩形的简单版本

简单之处：85题不允许排序，而此题允许排序

解法：贪心

13ms击败57.14%

时间复杂度O(m×n×logn)

参考85题的做法，我们可以枚举子矩形的底边，定义heights[j]：从matrix[i][j]往上有多少个连续的1，看成一根根柱子的高度

计算逻辑：如果matrix[i][j]=1，高度累加，否则高度重置为0

每次枚举子矩形的底边（每行），我们计算好此时的heights后将其升序排序，这样就能保证前小后大，我们仅需不断缩小范围，i从0到n的过程中，最矮的柱子即heights[i]，对应的面积为(n-i)*heights[i]，然后取这个过程的最大值即可，具体图解见下方答疑处

答疑

Q1：那统计时会不会出现如下图的情况，下面有一处空的，然后计算时把它“塌下去”计算呢？

不会的，因为我们枚举的是每一行，在当前行完成最大值更新，后续遇到0时会重置为0，而不会继续累加，计算过程如下图👇

优化

6ms击败100.00%

时间复杂度O(M×N)

我们在枚举每一行时会发现，其实排序不是一直必须的，如下图变化：

第一行排序过后为[0,0,1,1]，第二行在此基础上+1后变为[0,0,2,2]，这个过程就无需排序了，因为对于其中的[1,1]和[2,2]来说，“他们的相对大小不变”

因此得出结论：“上一行已经排好序的列，只要下一行不变成0，它们的相对大小顺序不会变”

所以我们只要已知第 i -1行heights排序后的结果，那么对于第 i 行，我们只需将高度变成0的数据排在前面，其余增加1的高度相对大小不变，就无需排序，这样就可以达到优化的效果，将时间复杂度从O(n log n)优化到O(N)

但是直接进行一次排序，时间复杂度还是不能达到优化的效果，怎样解决呢？

我们可以创建一个0~n-1的下标数组，对下标进行排序

每次先遍历上一轮已排好序的列号，将变成0的下标放在idx数组里，将非0高度的下标放在nonzeros数组里，最后将二者拼接：idx=idx+nonzeros，即可得到一个在heights中升序的下标数组，比如heights=[0,1,0,1,3,2]，那么idx=[0,2,1,3,5,4]

由于nonzeros中高度均>0，因此我们可以一边拼接一边更新最大值

Java代码：

class Solution {
public int largestSubmatrix(int[][] matrix) {
int m=matrix.length,n=matrix[0].length;
int ret=0;
int[] heights=new int[n];
for(int[] row:matrix){
for(int i=0;i<n;i++){
if(row[i]==1) heights[i]++;
else heights[i]=0;
}
//为保证heights能够继续正常计数，不串位，需要重新拷贝出来一个用来判断
int[] hs=heights.clone();
Arrays.sort(hs);
for(int i=0;i<n;i++)
ret=Math.max(ret,(n-i)*hs[i]);
}
return ret;
}
}
class Solution {
//优化版
public int largestSubmatrix(int[][] matrix) {
int n=matrix[0].length;
int[] heights=new int[n];
//idx数组：存储列号，后续按heights[idx[i]]升序排序，避免频繁排序
int[] idx=new int[n];
//初始时按0,1,……,n-1排序
for(int i=0;i<n;i++) idx[i]=i;
int[] nonzeros=new int[n];
int ret=0;
for(int[] row:matrix){
//p:记录idx数组中高度为0的列号的存放位置，前p个位置存0高度列
int p=0;
//q:记录nonzeros数组中高度非0的列号的存放位置
int q=0;
//遍历上一轮排序后的列号
for(int i:idx){
if(row[i]==0){
//当前列i在本行是0，高度重置为0
heights[i]=0;
//0高度的列号存进前p位
idx[p++]=i;
}else{
//当前列i在本行是1，高度累加
heights[i]++;
//非0高度的列号临时存到nonzeros数组
nonzeros[q++]=i;
}
}
//此时idx前p位是0高度列，接下来把nonzeros的非0高度列挪到idx的[p,n-1]位
//填充后，由于上一轮已经排好了序，本轮仅重置0高度列，因此heights[idx[i]]从idx[i]开始是升序的
for(int i=p;i<n;i++){
//填充
idx[i]=nonzeros[i-p];
//更新最大面积
ret=Math.max(ret,(n-i)*heights[idx[i]]);
}
}
return ret;
}
}