面积最大的全1子矩阵

题目见这里

这个题目就是枚举搜索,找最大值。以行为例,在每一行中找到每一个左边界,然后枚举以该左边界为边界的线段,这是第一步,然后以该线段长度分别向上和向下扫描,找到上边界和下边界,然后求值,如果当前值比max大,则更新max。比如下面矩阵:

0 1 1 1
0 1 1 1
1 1 1 1
1 1 0 1

以第一行为例,左边界为[0,1],以该点为左边界的线段有3个:[0,1]-[0,1],[0,1]-[0,2],[0,1]-[0,3],对于每一个线段,分别看上边界和下边界,看相邻上一行此范围的点是否都为1,如果是,则继续向上扫描。以[0,1]-[0,1]为例,上边界就是当前值,无需继续扫描,对于下边界,首先看[1,1]-[1,1],这个范围内的点都是1,则满足,然后继续扫描,即[x,1]-[x,1],枚举x从0到3,看这个范围内的点是否都为1,一直到不满足条件为止。

这就是基本思路,但是搜索中需要在2个地方优化。首先是枚举线段长度,这个可以通过一次预处理来优化,而不是每次都需要从左到右统计,用index[i][j]记录如下:

for (i = 0; i < m; ++i)
{
    for(cur = 0, j = 0; j < n; ++j)
    {
        if (matrix[i][j] == 0)
            index[i][j] = cur = 0;
        else
            index[i][j] = ++ cur;
    }
}

index[i][j]中记录的就是以[i,j]为线段右边界时,该线段的最大长度。

然后就是上下扫描优化,注意我们需要求的是该线段向上和向下分别最多能覆盖多少。如果以某一列为例,会发现有这样的特性:比如在求上边界时,如果index[i-1][j]大于index[i][j],说明[i,j]这个线段上边界一定不会在[i-1,j]的上边界的下面,就是说长线段一定能覆盖短线段。还是以上面的矩阵为例,比如index[3][3]为1,index[2][3]为3,那么[3,3]的上边界一定是在[2,3]的上边界的上面。而且这个过程可以循环下去,一直到找到上边界为止。

这个优化同并查集的路径优化很类似,就是比如知道A > B,同时B > C,那么我们可以推出A > C一样。这样就可以把一列的上下边界在O(m)时间内全部解决,比单纯的扫描方式提升了一个数量级。代码如下:

for(i = 0; i < n; ++i)
{
    for(j = 0; j < m; ++j)
    {
        up[j] = j;
        while(up[j] > 0 && index[up[j]-1][i] >= index[j][i])
            up[j] = up[up[j]-1];
    }
    for(j = m-1; j >= 0; --j)
    {
        down[j] = j;
        while(down[j]+1 < m && index[down[j]+1][i] >= index[j][i])
            down[j] = down[down[j]+1];
    }
    for(j = 0; j < m; ++j)
    {
        cur = (down[j] - up[j] + 1) * index[j][i];
        if(cur > max)
            max = cur;
    }
}

最后面就是对每一个矩阵进行枚举求大小,找最大值即可。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,788评论 0 33
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,803评论 18 399
  • thiele插值算法 1点插值算法 function [C,c]=thiele(X,Y,Z)%X为插值点横坐标,Y...
    00crazy00阅读 2,067评论 0 4
  • 幼儿教育是当今社会、家庭教育投资愈来愈多的行业,而幼教用品的发展毋庸置疑成为商家关注的焦点。近几年北京国际幼教用品...
    时光翩然阅读 226评论 0 0
  • 要说起三五小姐和七七小姐的第一次见面,第一次搭话,真的是羞涩又陌生。 她们跟大多数的大学生们一样,爸妈护送,带着一...
    星莘惜阅读 229评论 0 1