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.开始在弹出的界面中将鼠标切换到常规…