19.2.23 [LeetCode 85] Maximal Rectangle

发布时间：2020-12-14 04:23:30 所属栏目：大数据来源：网络整理

导读：Given a 2D binary matrix filled with 0‘s and 1‘s,find the largest rectangle containing only 1‘s and return its area. Example: Input:[ ["1","0","1","0"],["1","1"],"0"]]Output: 6 题意找图中由1组成的最大矩形题解 1 class Solution { 2 publ

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

Example:

Input:
[
  ["1","0","1","0"],["1","1"],"0"]
]
Output: 6

题意

找图中由1组成的最大矩形

题解

 1 class Solution {
 2 public:
 3     int maximalRectangle(vector<vector<char>>& matrix) {
 4         if (matrix.empty())return 0;
 5         int m = matrix.size(),n = matrix[0].size(),ans = 0;
 6         vector<int>height(n,0),left(n,0),right(n,n);
 7         for (int i = 0; i < m; i++) {
 8             int s = 0;
 9             for (int j = 0; j < n; j++) {
10                 if (matrix[i][j] == ‘0‘) {
11                     height[j] = 0;
12                     left[j] = 0;
13                     s = j + 1;
14                 }
15                 else {
16                     left[j] = max(left[j],s);
17                     height[j]++;
18                 }
19             }
20             int e = n - 1;
21             for (int j = n - 1; j >= 0; j--) {
22                 if (matrix[i][j] == ‘0‘) {
23                     right[j] = n;
24                     e = j - 1;
25                 }
26                 else {
27                     right[j] = min(right[j],e);
28                 }
29             }
30             for (int j = 0; j < n; j++)
31                 if (matrix[i][j] == ‘1‘)
32                     ans = max(ans,(right[j] - left[j] + 1)*height[j]);
33         }
34         return ans;
35     }
36 };

View Code

这题好难的……

思路是找到三个数组?height[x]?代表从当前行的x索引表示的元素往上数能数到多少连续的1,?left[x]?表示当前行的x索引往左边数能数到多少个连续的height值>=它自己的1,?right[x]?与left相仿（这些计数均包括当前索引且如果当前索引的值为0则这三个数组相应的值无意义）

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!