Maximal Rectangle
Maximal Rectangle
曾劲松 发表于1年前
Maximal Rectangle
  • 发表于 1年前
  • 阅读 10
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

对于点A,H[1] = 4, L[1] = 1, R[1] = 2。对应的矩形面积H * (R - L) = 4。

对于点B,H[2] = 3, L[2] = 1, R[2] = 4。对应的矩形面积H * (R - L) = 9。

int maximalRectangle(vector<vector<char> > &matrix){
          if(matrix.size() == 0 || matrix[0].size() == 0)
          return 0;
        
          int m = matrix.size(), n = matrix[0].size(), res = 0;
          vector<int> left(n, 0), right(n, n), height(n, 0);
        
          for(int i = 0; i < m; ++ i){
              int cur_left = 0, cur_right = n;
            
              for(int j = 0; j < n; ++ j) {
                 height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
                 left[j] = matrix[i][j] == '1' ? max(left[j], cur_left) : 0;
                 cur_left = matrix[i][j] == '1' ? cur_left : j + 1;
              }
             
              for(int j = n - 1; j >= 0; -- j){
                 right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
                cur_right = matrix[i][j] == '1' ? cur_right : j;
              }
            
              for(int j = 0; j < n; ++ j)
                 res = max(res, (right[j] - left[j]) * height[j]);
              }
        
          return res;
     }

 

共有 人打赏支持
粉丝 4
博文 132
码字总数 141022
×
曾劲松
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: