C++如何实现最大矩形

这篇文章主要讲解了“C++如何实现最大矩形”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++如何实现最大矩形”吧!Example:Input:
[
[“1″,”0″,”1″,”0″,”0”],
[“1″,”0″,”1″,”1″,”1”],
[“1″,”1″,”1″,”1″,”1”],
[“1″,”0″,”0″,”1″,”0”]
]
Output: 6此题是之前那道的Largest Rectangle in Histogram的扩展,这道题的二维矩阵每一层向上都可以看做一个直方图,输入矩阵有多少行,就可以形成多少个直方图,对每个直方图都调用Largest Rectangle in Histogram中的方法,就可以得到最大的矩形面积。那么这道题唯一要做的就是将每一层都当作直方图的底层,并向上构造整个直方图,由于题目限定了输入矩阵的字符只有 “0” 和 “1” 两种,所以处理起来也相对简单。方法是,对于每一个点,如果是 ‘0″,则赋0,如果是 ‘1″,就赋之前的 height 值加上1。具体参见代码如下:解法一:我们也可以在一个函数内完成,这样代码看起来更加简洁一些,注意这里的 height 初始化的大小为 n+1,为什么要多一个呢?这是因为我们只有在当前位置小于等于前一个位置的高度的时候,才会去计算矩形的面积,假如最后一个位置的高度是最高的,那么我们就没法去计算并更新结果 res 了,所以要在最后再加一个高度0,这样就一定可以计算前面的矩形面积了,这跟上面解法子函数中给 height 末尾加一个0是一样的效果,参见代码如下:解法二:下面这种方法的思路很巧妙,height 数组和上面一样,这里的 left 数组表示若当前位置是1且与其相连都是1的左边界的位置(若当前 height 是0,则当前 left 一定是0),right 数组表示若当前位置是1且与其相连都是1的右边界的位置再加1(加1是为了计算长度方便,直接减去左边界位置就是长度),初始化为n(若当前 height 是0,则当前 right 一定是n),那么对于任意一行的第j个位置,矩形为 (right[j] – left[j]) * height[j],我们举个例子来说明,比如给定矩阵为:第0行:h: 1 1 0 0 1l: 0 0 0 0 4r: 2 2 5 5 5第1行:h:0 2 0 0 2l: 0 1 0 0 4r: 5 2 5 5 5第2行:h: 0 0 1 1 3l: 0 0 2 2 4r: 5 5 5 5 5第3行:h: 0 0 2 2 4l: 0 0 2 2 4r: 5 5 5 5 5第4行:h: 0 0 0 0 5l: 0 0 0 0 4r: 5 5 5 5 5解法三:再来看一种解法,这里我们统计每一行的连续1的个数,使用一个数组 h_max, 其中 h_max[i][j] 表示第i行,第j个位置水平方向连续1的个数,若 matrix[i][j] 为0,那对应的 h_max[i][j] 也一定为0。统计的过程跟建立累加和数组很类似,唯一不同的是 香港云主机遇到0了要将 h_max 置0。这个统计好了之后,只需要再次遍历每个位置,首先每个位置的 h_max 值都先用来更新结果 res,因为高度为1也可以看作是矩形,然后我们向上方遍历,上方 (i, j-1) 位置也会有 h_max 值,但是用二者之间的较小值才能构成矩形,用新的矩形面积来更新结果 res,这样一直向上遍历,直到遇到0,或者是越界的时候停止,这样就可以找出所有的矩形了,参见代码如下:解法四:感谢各位的阅读,以上就是“C++如何实现最大矩形”的内容了,经过本文的学习后,相信大家对C++如何实现最大矩形这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是开发云,小编将为大家推送更多相关知识点的文章,欢迎关注!

相关推荐: 怎么在电脑中找到IE缓存文件夹

这篇文章给大家分享的是有关怎么在电脑中找到IE缓存文件夹的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。解决方法/步骤:1.直接打开电脑中的IE浏览器,随后点击工具并选择internet选项进入。2.开始在弹出的界面中将鼠标切换到常规…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 07/14 16:22
下一篇 07/14 16:22

相关推荐

发表评论

您的电子邮箱地址不会被公开。