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","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6
Solution: DP
Time complexity: O(m^2*n)
Space complexity: O(mn)
dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row.
transition:
dp[i][j] = 0 if matrix[i][j] == ‘0’
= dp[i][j-1] + 1 if matrix[i][j] == ‘1’
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { int r = matrix.size(); if (r == 0) return 0; int c = matrix[0].size(); // dp[i][j] := max len of all 1s ends with col j at row i. vector<vector<int>> dp(r, vector<int>(c)); for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) dp[i][j] = (matrix[i][j] == '1') ? (j == 0 ? 1 : dp[i][j - 1] + 1) : 0; int ans = 0; for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) { int len = INT_MAX; for (int k = i; k < r; k++) { len = min(len, dp[k][j]); if (len == 0) break; ans = max(len * (k - i + 1), ans); } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment