首页 > 代码库 > LeetCode: Maximal Rectangle

LeetCode: Maximal Rectangle

2024-07-21 00:52:10   225人阅读

LeetCode: Maximal Rectangle

Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing all ones and return its area.

地址：https://oj.leetcode.com/problems/maximal-rectangle/

算法：要解决这道题，得利用Largest Rectangle in Histogram这道题的解法。我们把矩阵的每一行都看成histogram‘s bar的底，比如第i行可以看成从最后一行到第i行之间的histogram，并且每一列的高度为在该列上从i行开始向下数连续为1的行数。这样以第i行为矩阵的上面一条边的最大矩阵的值即为这个histogram中最大的矩阵面积。也就是说对于没一个行，我们都可以计算出该行所代表的histogram，然后调用Largest Rectangle in Histogram里面的函数就可以找出以该行为上边的最大矩阵，然后从所有行中找到整个问题的最大矩阵。代码：

 1 class Solution { 2 public: 3     int maximalRectangle(vector<vector<char> > &matrix) { 4         if(matrix.empty() || matrix[0].empty()) return 0; 5         int row_num = matrix.size(); 6         int col_num = matrix[0].size(); 7         vector<int> histogram1(col_num), histogram2(col_num); 8         for(int j = 0; j < col_num; ++j){ 9             histogram1[j] = matrix[row_num-1][j] - ‘0‘;10         }11         int max_area = largestRectangleArea(histogram1);12         vector<int> *p_now = &histogram2;13         vector<int> *p_pre = &histogram1;14         for(int i = row_num-2; i >= 0; --i){15             for(int j = 0; j < col_num; ++j){16                 if(matrix[i][j] == ‘0‘){17                     (*p_now)[j] = 0;18                 }else if(matrix[i+1][j] == matrix[i][j]){19                     (*p_now)[j] = (*p_pre)[j] + 1;20                 }else{21                     (*p_now)[j] = 1;22                 }23             }24             int area = largestRectangleArea(*p_now);25             if(area > max_area)26                 max_area = area;27             vector<int> *temp = p_now;28             p_now = p_pre;29             p_pre = temp;30         }31         return max_area;32     }33     int largestRectangleArea(vector<int> &height) {34         int len = height.size();35         if(len < 1) return 0;36         stack<int> stk;37         int i = 0;38         int max_area = 0;39         while(i < len){40             if(stk.empty() || height[stk.top()] <= height[i]){41                 stk.push(i++);42             }else{43                 int t = stk.top();44                 stk.pop();45                 int area = height[t] * (stk.empty() ? i : i - stk.top() - 1);46                 if(area > max_area){47                     max_area = area;48                 }49             }50         }51         while(!stk.empty()){52             int t = stk.top();53             stk.pop();54             int area = height[t] * (stk.empty() ? len : len - stk.top() - 1);55             if(area > max_area){56                 max_area = area;57             }58         }59         return max_area;60     }61 };

 

LeetCode: Maximal Rectangle


联系
我们