C++刷LeetCode（85. 最大矩形）【动态规划】

糖逗

题目描述：

1. 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
   
2. 
   
3. 示例:
   
4. 
   
5. 输入:
   
6. [
   
7.   ["1","0","1","0","0"],
   
8.   ["1","0","1","1","1"],
   
9.   ["1","1","1","1","1"],
   
10.   ["1","0","0","1","0"]
    
11. ]
    
12. 输出: 6

复制代码

1. class Solution {
   
2. public:
   
3.     struct compair{
   
4.         int up;
   
5.         int left;
   
6.     };
   
7.     int maximalRectangle(vector<vector<char>>& matrix) {
   
8.         if(matrix.empty()) return 0;
   
9.         int len1 = matrix.size(), len2 = matrix[0].size();
   
10.         vector<vector<compair> >dp(len1 + 1, vector<compair>(len2 + 1, {0, 0}));
    
11.         int res = 0;
    
12.         for(int i = 1; i <= len1; i++){
    
13.             for(int j = 1; j <= len2; j++){
    
14.                 if(matrix[i - 1][j - 1] != '1') continue;
    
15.                 dp[i][j].up = dp[i-1][j].up + 1;
    
16.                 dp[i][j].left = dp[i][j-1].left + 1;
    
17.                 int store1 = dp[i][j].left;
    
18.                 int number1 = 1;
    
19.                 for(int m = i; m >= i - dp[i][j].up + 1; m--){
    
20.                     store1 = min(store1, dp[m][j].left);
    
21.                     res = max(res, store1 * number1);
    
22.                     number1++;
    
23.                 }
    
24.                 int store2 = dp[i][j].up;
    
25.                 int number2 = 1;
    
26.                 for(int n = j; n >= j - dp[i][j].left + 1; n--){
    
27.                     store2 = min(store2, dp[i][n].up);
    
28.                     res = max(res, store2 *number2);
    
29.                     number2++;
    
30.                 }
    
31.             }
    
32.         }
    
33.         return res;
    
34.     }
    
35. };

复制代码

糖逗

类比：https://fishc.com.cn/forum.php?m ... =%D5%FD%B7%BD%D0%CE
https://fishc.com.cn/forum.php?m ... =%D5%FD%B7%BD%D0%CE

糖逗