diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /maximal_rectangle.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'maximal_rectangle.py')
-rw-r--r-- | maximal_rectangle.py | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/maximal_rectangle.py b/maximal_rectangle.py new file mode 100644 index 0000000..5e18d0c --- /dev/null +++ b/maximal_rectangle.py @@ -0,0 +1,44 @@ +# 85. Maximal Rectangle + +""" +given a 'rows * cols' binary 'matrix' filled with 0's and 1's, find the +largest rectangle containing only 1's and return its area. +""" + + +class Solution(object): + def maximalRectangle(self, matrix): + """ + :type matrix: List[List[str]] + :rtype: int + """ + if not matrix or not matrix[0]: + return 0 + n = len(matrix[0]) + height = [0] * (n + 1) + ans = 0 + for row in matrix: + for i in range(n): + height[i] = height[i] + 1 if row[i] == "1" else 0 + stack = [-1] + for i in range(n + 1): + while height[i] < height[stack[-1]]: + h = height[stack.pop()] + w = i - 1 - stack[-1] + ans = max(ans, h * w) + stack.append(i) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maximalRectangle( + matrix=[ + ["1", "0", "1", "0", "0"], + ["1", "0", "1", "1", "1"], + ["1", "1", "1", "1", "1"], + ["1", "0", "0", "1", "0"], + ] + ) + ) |