算法设计（如何计算全为1的最大矩形二进制子矩阵（））

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
Java
Python3
C#

给定一个二进制矩阵, 找到全为1的最大尺寸的矩形二进制子矩阵。
例子：

Input:0 1 1 01 1 1 11 1 1 11 1 0 0Output :1 1 1 11 1 1 1Explanation : The largest rectangle with only 1's is from (1, 0) to (2, 3) which is1 1 1 11 1 1 1 Input:0 1 11 1 10 1 1Output:1 11 11 1Explanation : The largest rectangle with only 1's is from (0, 1) to (2, 2) which is1 11 11 1

推荐：请在"实践首先, 在继续解决方案之前。已经有讨论过的算法了基于动态编程的解决方案, 以寻找最大的平方与1.
方法：
在这篇文章中, 讨论了一种有趣的方法, 该方法使用
直方图下的最大矩形
作为子例程。
如果给出直方图的条形高度, 则可以找到直方图的最大面积。这样, 在每一行中, 可以找到直方图的最大条形区域。要使最大的矩形充满1, 请在上一行的基础上更新下一行, 并在直方图下找到最大的面积, 即, 将每个1填充为正方形, 将0填充为一个空正方形, 并将每行作为底数。
插图：

Input :0 1 1 01 1 1 11 1 1 11 1 0 0Step 1: 0 1 1 0maximum area= 2Step 2:row 11 2 2 1area = 4, maximum area becomes 4row 22 3 3 2area = 8, maximum area becomes 8row 33 4 0 0area = 6, maximum area remains 8

算法：

运行循环以遍历各行。
现在, 如果当前行不是第一行, 则按如下方式更新该行, 如果matrix [i] [j]不为零, 则matrix [i] [j] = matrix [i-1] [j] + matrix [i ] [j]。
找到直方图下方的最大矩形区域, 将第i行视为直方图的条形高度。可以按照本文给出的方法进行计算直方图中最大的矩形区域
对所有行执行前两个步骤, 并打印所有行的最大面积。

注意
：强烈建议参考
这个
首先发布, 因为大多数代码是从那里获取的。
实现
C ++

// C++ program to find largest rectangle with all 1s // in a binary matrix #include < bits/stdc++.h> using namespace std; // Rows and columns in input matrix #define R 4 #define C 4// Finds the maximum area under the histogram represented // by histogram.See below article for details. // https:// www.lsbin.org/largest-rectangle-under-histogram/ int maxHist( int row[]) { // Create an empty stack. The stack holds indexes of // hist[] array/ The bars stored in stack are always // in increasing order of their heights. stack< int > result; int top_val; // Top of stackint max_area = 0; // Initialize max area in current // row (or histogram)int area = 0; // Initialize area with current top// Run through all bars of given histogram (or row) int i = 0; while (i < C) { // If this bar is higher than the bar on top stack, // push it to stack if (result.empty() || row[result.top()] < = row[i]) result.push(i++); else { // If this bar is lower than top of stack, then // calculate area of rectangle with stack top as // the smallest (or minimum height) bar. 'i' is // 'right index' for the top and element before // top in stack is 'left index' top_val = row[result.top()]; result.pop(); area = top_val * i; if (!result.empty()) area = top_val * (i - result.top() - 1); max_area = max(area, max_area); } }// Now pop the remaining bars from stack and calculate area // with every popped bar as the smallest bar while (!result.empty()) { top_val = row[result.top()]; result.pop(); area = top_val * i; if (!result.empty()) area = top_val * (i - result.top() - 1); max_area = max(area, max_area); } return max_area; }// Returns area of the largest rectangle with all 1s in A[][] int maxRectangle( int A[][C]) { // Calculate area for first row and initialize it as // result int result = maxHist(A[0]); // iterate over row to find maximum rectangular area // considering each row as histogram for ( int i = 1; i < R; i++) {for ( int j = 0; j < C; j++)// if A[i][j] is 1 then add A[i -1][j] if (A[i][j]) A[i][j] += A[i - 1][j]; // Update result if area with current row (as last row) // of rectangle) is more result = max(result, maxHist(A[i])); }return result; }// Driver code int main() { int A[][C] = { { 0, 1, 1, 0 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 0, 0 }, }; cout < < "Area of maximum rectangle is " < < maxRectangle(A); return 0; }

Java

// Java program to find largest rectangle with all 1s // in a binary matrix import java.io.*; import java.util.*; class GFG { // Finds the maximum area under the histogram represented // by histogram.See below article for details. // https:// www.lsbin.org/largest-rectangle-under-histogram/ static int maxHist( int R, int C, int row[]) { // Create an empty stack. The stack holds indexes of // hist[] array/ The bars stored in stack are always // in increasing order of their heights. Stack< Integer> result = new Stack< Integer> (); int top_val; // Top of stackint max_area = 0 ; // Initialize max area in current // row (or histogram)int area = 0 ; // Initialize area with current top// Run through all bars of given histogram (or row) int i = 0 ; while (i < C) { // If this bar is higher than the bar on top stack, // push it to stack if (result.empty() || row[result.peek()] < = row[i]) result.push(i++); else { // If this bar is lower than top of stack, then // calculate area of rectangle with stack top as // the smallest (or minimum height) bar. 'i' is // 'right index' for the top and element before // top in stack is 'left index' top_val = row[result.peek()]; result.pop(); area = top_val * i; if (!result.empty()) area = top_val * (i - result.peek() - 1 ); max_area = Math.max(area, max_area); } }// Now pop the remaining bars from stack and calculate // area with every popped bar as the smallest bar while (!result.empty()) { top_val = row[result.peek()]; result.pop(); area = top_val * i; if (!result.empty()) area = top_val * (i - result.peek() - 1 ); max_area = Math.max(area, max_area); } return max_area; }// Returns area of the largest rectangle with all 1s in // A[][] static int maxRectangle( int R, int C, int A[][]) { // Calculate area for first row and initialize it as // result int result = maxHist(R, C, A[ 0 ]); // iterate over row to find maximum rectangular area // considering each row as histogram for ( int i = 1 ; i < R; i++) {for ( int j = 0 ; j < C; j++)// if A[i][j] is 1 then add A[i -1][j] if (A[i][j] == 1 ) A[i][j] += A[i - 1 ][j]; // Update result if area with current row (as last // row of rectangle) is more result = Math.max(result, maxHist(R, C, A[i])); }return result; }// Driver code public static void main(String[] args) { int R = 4 ; int C = 4 ; int A[][] = { { 0 , 1 , 1 , 0 }, { 1 , 1 , 1 , 1 }, { 1 , 1 , 1 , 1 }, { 1 , 1 , 0 , 0 }, }; System.out.print( "Area of maximum rectangle is " + maxRectangle(R, C, A)); } }// Contributed by Prakriti Gupta

Python3

# Python3 program to find largest rectangle # with all 1s in a binary matrix # Rows and columns in input matrix R = 4 C = 4# Finds the maximum area under the histogram represented # by histogram. See below article for details. # https:# www.lsbin.org / largest-rectangle-under-histogram / def maxHist(row):# Create an empty stack. The stack holds # indexes of hist array / The bars stored # in stack are always in increasing order # of their heights. result = []top_val = 0# Top of stack max_area = 0 # Initialize max area in current # row (or histogram) area = 0 # Initialize area with current top # Run through all bars of given # histogram (or row) i = 0 while (i < C): # If this bar is higher than the # bar on top stack, push it to stack if ( len (result) = = 0 ) or (row[result[ 0 ]] < = row[i]): result.append(i) i + = 1 else :# If this bar is lower than top of stack, # then calculate area of rectangle with # stack top as the smallest (or minimum # height) bar. 'i' is 'right index' for # the top and element before top in stack # is 'left index' top_val = row[result[ 0 ]] result.pop( 0 ) area = top_val * i if ( len (result)): area = top_val * (i - result[ 0 ] - 1 ) max_area = max (area, max_area) # Now pop the remaining bars from stack # and calculate area with every popped # bar as the smallest bar while ( len (result)): top_val = row[result[ 0 ]] result.pop( 0 ) area = top_val * i if ( len (result)): area = top_val * (i - result[ 0 ] - 1 ) max_area = max (area, max_area) return max_area # Returns area of the largest rectangle # with all 1s in A def maxRectangle(A):# Calculate area for first row and # initialize it as result result = maxHist(A[ 0 ]) # iterate over row to find maximum rectangular # area considering each row as histogram for i in range ( 1 , R):for j in range (C):# if A[i][j] is 1 then add A[i -1][j] if (A[i][j]): A[i][j] + = A[i - 1 ][j] # Update result if area with current # row (as last row) of rectangle) is more result = max (result, maxHist(A[i])) return result # Driver Code if __name__ = = '__main__' : A = [[ 0 , 1 , 1 , 0 ], [ 1 , 1 , 1 , 1 ], [ 1 , 1 , 1 , 1 ], [ 1 , 1 , 0 , 0 ]] print ( "Area of maximum rectangle is" , maxRectangle(A))# This code is contributed # by SHUBHAMSINGH10

// C# program to find largest rectangle // with all 1s in a binary matrix using System; using System.Collections.Generic; class GFG { // Finds the maximum area under the // histogram represented by histogram. // See below article for details. // https:// www.lsbin.org/largest-rectangle-under-histogram/ public static int maxHist( int R, int C, int [] row) { // Create an empty stack. The stack // holds indexes of hist[] array. // The bars stored in stack are always // in increasing order of their heights. Stack< int > result = new Stack< int > (); int top_val; // Top of stackint max_area = 0; // Initialize max area in // current row (or histogram)int area = 0; // Initialize area with // current top// Run through all bars of // given histogram (or row) int i = 0; while (i < C) { // If this bar is higher than the // bar on top stack, push it to stack if (result.Count == 0 || row[result.Peek()] < = row[i]) { result.Push(i++); }else { // If this bar is lower than top // of stack, then calculate area of // rectangle with stack top as // the smallest (or minimum height) // bar. 'i' is 'right index' for // the top and element before // top in stack is 'left index' top_val = row[result.Peek()]; result.Pop(); area = top_val * i; if (result.Count > 0) { area = top_val * (i - result.Peek() - 1); } max_area = Math.Max(area, max_area); } }// Now pop the remaining bars from // stack and calculate area with // every popped bar as the smallest bar while (result.Count > 0) { top_val = row[result.Peek()]; result.Pop(); area = top_val * i; if (result.Count > 0) { area = top_val * (i - result.Peek() - 1); }max_area = Math.Max(area, max_area); } return max_area; }// Returns area of the largest // rectangle with all 1s in A[][] public static int maxRectangle( int R, int C, int [][] A) { // Calculate area for first row // and initialize it as result int result = maxHist(R, C, A[0]); // iterate over row to find // maximum rectangular area // considering each row as histogram for ( int i = 1; i < R; i++) { for ( int j = 0; j < C; j++) {// if A[i][j] is 1 then // add A[i -1][j] if (A[i][j] == 1) { A[i][j] += A[i - 1][j]; } }// Update result if area with current // row (as last row of rectangle) is more result = Math.Max(result, maxHist(R, C, A[i])); }return result; }// Driver code public static void Main( string [] args) { int R = 4; int C = 4; int [][] A = new int [][] { new int [] { 0, 1, 1, 0 }, new int [] { 1, 1, 1, 1 }, new int [] { 1, 1, 1, 1 }, new int [] { 1, 1, 0, 0 } }; Console.Write( "Area of maximum rectangle is " + maxRectangle(R, C, A)); } }// This code is contributed by Shrikant13

输出：

Area of maximum rectangle is 8

复杂度分析：

时间复杂度：O(R x C)。
矩阵只需要遍历一次, 因此时间复杂度为O(R X C)
空间复杂度：O(C)。
需要使用堆栈来存储列, 因此空间复杂度为O(C)

本文由Sanjiv Kumar贡献。如果你喜欢lsbin并希望做出贡献, 那么你也可以写一篇文章并将你的文章邮寄到contribution@lsbin.org。查看你的文章出现在lsbin主页上, 并帮助其他Geeks。
【算法设计（如何计算全为1的最大矩形二进制子矩阵（））】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。