糖逗 发表于 2020-6-29 13:45:26

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

题目描述：
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6



class Solution {
public:
    struct compair{
      int up;
      int left;
    };
    int maximalRectangle(vector<vector<char>>& matrix) {
      if(matrix.empty()) return 0;
      int len1 = matrix.size(), len2 = matrix.size();
      vector<vector<compair> >dp(len1 + 1, vector<compair>(len2 + 1, {0, 0}));
      int res = 0;
      for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(matrix != '1') continue;
                dp.up = dp.up + 1;
                dp.left = dp.left + 1;
                int store1 = dp.left;
                int number1 = 1;
                for(int m = i; m >= i - dp.up + 1; m--){
                  store1 = min(store1, dp.left);
                  res = max(res, store1 * number1);
                  number1++;
                }
                int store2 = dp.up;
                int number2 = 1;
                for(int n = j; n >= j - dp.left + 1; n--){
                  store2 = min(store2, dp.up);
                  res = max(res, store2 *number2);
                  number2++;
                }
            }
      }
      return res;
    }
};

糖逗 发表于 2020-6-29 13:45:59

类比：https://fishc.com.cn/forum.php?mod=viewthread&tid=173113&highlight=%D5%FD%B7%BD%D0%CE
https://fishc.com.cn/forum.php?mod=viewthread&tid=168254&highlight=%D5%FD%B7%BD%D0%CE

糖逗 发表于 2020-6-29 13:46:35

{:10_298:}
页: [1]
查看完整版本: C++刷LeetCode（85. 最大矩形）【动态规划】