首页 > 代码库 > leetcode - Maximal Rectangle
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.
class Solution { public: int largestRectangleArea(int* height, int length) { std::stack<int> s; int i = 0; int maxArea = 0; while(i < length){ if(s.empty() || height[s.top()] <= height[i]){ s.push(i++); }else { int t = s.top(); s.pop(); int area = height[t] * (s.empty() ? i : i - s.top() - 1); maxArea = maxArea > area ? maxArea : area; } } return maxArea; } int maximalRectangle(std::vector<std::vector<char> > &matrix) { int m = matrix.size(); if(m == 0)return 0; int n = matrix[0].size(); if(n == 0)return 0; int** dp = new int*[m]; for(int i = 0; i < m; ++i){ dp[i] = new int[n+1]; memset(dp[i], 0, sizeof(int)*(n+1)); } for(int j = 0; j < n; ++j) if(matrix[0][j] == '1')dp[0][j] = 1; for(int j = 0; j < n; ++j) for(int i = 1; i < m; ++i) if(matrix[i][j] == '1') dp[i][j] = dp[i-1][j] + 1; int maxArea = 0; for(int i = 0; i < m; ++i){ int tmp = largestRectangleArea(dp[i],n+1); if(tmp > maxArea) maxArea = tmp; } for(int i = 0; i < m; ++i) delete[] dp[i]; delete[] dp; return maxArea; } };
leetcode - Maximal Rectangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。