# 全為 1 的最大尺寸矩形二進制子矩陣 > 原文： [https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/](https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/) 給定一個二進制矩陣，找到最大大小為 1 的矩形 binary-sub-matrix。 **例如**： ``` Input: 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 Output : 1 1 1 1 1 1 1 1 Explanation : The largest rectangle with only 1's is from (1, 0) to (2, 3) which is 1 1 1 1 1 1 1 1 Input: 0 1 1 1 1 1 0 1 1 Output: 1 1 1 1 1 1 Explanation : The largest rectangle with only 1's is from (0, 1) to (2, 2) which is 1 1 1 1 1 1 ``` *已經有一種算法討論了一種基于[動態編程的解決方案，用于尋找 1s 的最大平方](https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/)。* **方法**：在本文中討論了一種有趣的方法，該方法將直方圖下的[最大矩形用作子例程。 如果給出直方圖的條形高度，則可以找到直方圖的最大面積。 這樣，在每一行中，可以找到直方圖的最大條形區域。 要使最大的矩形充滿 1，請在上一行的基礎上更新下一行，并在直方圖下找到最大的面積，即，將每個 1 填充為正方形，將 0 填充為一個空正方形，并以每行為基礎。](https://www.geeksforgeeks.org/largest-rectangle-under-histogram/) **插圖**： ``` Input : 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 Step 1: 0 1 1 0 maximum area = 2 Step 2: row 1 1 2 2 1 area = 4, maximum area becomes 4 row 2 2 3 3 2 area = 8, maximum area becomes 8 row 3 3 4 0 0 area = 6, maximum area remains 8 ``` **算法**： 1. 運行循環以遍歷各行。 2. 現在，如果當前行不是第一行，則按如下方式更新該行，如果 matrix [i] [j]不為零，則 matrix [i] [j] = matrix [i-1] [j] + matrix [i ] [j]。 3. 找到直方圖下方的最大矩形區域，將第 i 行視為直方圖的條形高度。 可以按照本文給出的方法進行計算。[直方圖中的最大矩形區域](https://www.geeksforgeeks.org/largest-rectangle-under-histogram/) 4. 對所有行執行前兩個步驟，并打印所有行的最大面積。 *注*：強烈建議首先參考此帖子，因為那里的大多數代碼都來自此。 **實現** ## C++ ```cpp // 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.geeksforgeeks.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 stack ????int 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; } ```