leetcode

commit bf552552bb42f87e569d1a93d1fed20d1c80cd00
parent 35bc523af533220c03d188d6f5c1f8ed1439592c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 10 Jan 2026 18:27:03 -0700

85. maximal rectangle

Diffstat:
M
maximal_rectangle.c
 | 
86
++++++++++++++++++++++++++++++++++++++-----------------------------------------
M
maximal_rectangle.py
 | 
27
++++++++++++++-------------

2 files changed, 55 insertions(+), 58 deletions(-)
diff --git a/maximal_rectangle.c b/maximal_rectangle.c
@@ -6,57 +6,53 @@
  * largest rectangle containing only 1's and return its area.
  */
 
-int max_area(int *heights, int heights_size) {
-  int *stack = (int *)malloc(heights_size * sizeof(int));
-  int depth = 0, width = 0, res = 0, i = 0, tmp = 0;
-  if (!heights || !heights_size)
+int maximalRectangle(char **matrix, int matrixSize, int *matrixColSize) {
+  if (!matrixSize || !*matrixColSize)
     return 0;
-  while (i < heights_size) {
-    if (!depth || heights[i] >= heights[stack[depth - 1]]) {
-      stack[depth] = i;
-      depth++, i++;
-    } else {
-      while (depth && heights[stack[depth - 1]] > heights[i]) {
-        width = depth > 1 ? i - stack[depth - 2] - 1 : i;
-        tmp = heights[stack[depth - 1]] * width;
-        if (res < tmp)
-          res = tmp;
-        depth--;
+  int ans = 0;
+  int *height = (int *)calloc(*matrixColSize, sizeof(int));
+  int *left = (int *)calloc(*matrixColSize, sizeof(int));
+  int *right = (int *)malloc(*matrixColSize * sizeof(int));
+  for (int i = 0; i < *matrixColSize; i++)
+    right[i] = *matrixColSize;
+  for (int i = 0; i < matrixSize; i++) {
+    int curr_l = 0, curr_r = *matrixColSize;
+    for (int j = 0; j < *matrixColSize; j++) {
+      if (matrix[i][j] == '1') {
+        height[j]++;
+        left[j] = left[j] > curr_l ? left[j] : curr_l;
+      } else {
+        height[j] = left[j] = 0;
+        curr_l = j + 1;
       }
     }
+    for (int j = *matrixColSize - 1; j >= 0; j--) {
+      if (matrix[i][j] == '1')
+        right[j] = right[j] < curr_r ? right[j] : curr_r;
+      else {
+        right[j] = *matrixColSize;
+        curr_r = j;
+      }
+    }
+    for (int j = 0; j < *matrixColSize; j++)
+      ans = fmax(ans, (right[j] - left[j]) * height[j]);
   }
-  while (depth) {
-    width = depth > 1 ? i - stack[depth - 2] - 1 : i;
-    tmp = heights[stack[depth - 1]] * width;
-    if (res < tmp)
-      res = tmp;
-    depth--;
-  }
-  free(stack);
-  return res;
-}
-
-int maximalRectangle(char **matrix, int matrix_size, int *matrix_col_size) {
-  int *heights = (int *)calloc(*matrix_col_size, sizeof(int));
-  int ans = 0;
-  if (!matrix || !matrix_size)
-    return 0;
-  for (int i = 0; i < matrix_size; i++) {
-    for (int j = 0; j < *matrix_col_size; j++)
-      heights[j] = matrix[i][j] == '0' ? 0 : heights[j] + 1;
-    int tmp = max_area(heights, *matrix_col_size);
-    if (ans < tmp)
-      ans = tmp;
-  }
-  free(heights);
+  free(height);
+  free(left);
+  free(right);
   return ans;
 }
 
 int main() {
-  char *matrix[4][5] = {{"1", "0", "1", "0", "0"},
-                        {"1", "0", "1", "1", "1"},
-                        {"1", "1", "1", "1", "1"},
-                        {"1", "0", "0", "1", "0"}};
-  int matrix_col_size = 5;
-  printf("%d\n", maximalRectangle((char **)matrix, 4, &matrix_col_size));
+  char *m1[4][5] = {{"1", "0", "1", "0", "0"},
+                    {"1", "0", "1", "1", "1"},
+                    {"1", "1", "1", "1", "1"},
+                    {"1", "0", "0", "1", "0"}};
+  char *m2[1][1] = {{"0"}}, *m3[1][1] = {{"1"}};
+  printf("%d\n", maximalRectangle((char **)m1, ARRAY_SIZE(m1),
+                                  ARRAY_SIZE(m1i[0]))); // expect: 6
+  printf("%d\n", maximalRectangle((char **)m2, ARRAY_SIZE(m2),
+                                  ARRAY_SIZE(m2i[0]))); // expect: 0
+  printf("%d\n", maximalRectangle((char **)m3, ARRAY_SIZE(m3),
+                                  ARRAY_SIZE(m3i[0]))); // expect: 1
 }
diff --git a/maximal_rectangle.py b/maximal_rectangle.py
@@ -12,21 +12,20 @@ class Solution(object):
         :type matrix: List[List[str]]
         :rtype: int
         """
-        if not matrix or not matrix[0]:
+        if not matrix:
             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]
+        n, m = len(matrix), len(matrix[0])
+        heights, ans = [0] * (m + 1), 0
+        for i in matrix:
+            for j in range(m):
+                heights[j] = heights[j] + 1 if i[j] == "1" else 0
+            stack = []
+            for j in range(len(heights)):
+                while stack and heights[j] < heights[stack[-1]]:
+                    h = heights[stack.pop()]
+                    w = j if not stack else j - stack[-1] - 1
                     ans = max(ans, h * w)
-                stack.append(i)
+                stack.append(j)
         return ans
 
 
@@ -42,3 +41,5 @@ if __name__ == "__main__":
             ]
         )
     )
+    print(obj.maximalRectangle(matrix=[["0"]]))
+    print(obj.maximalRectangle(matrix=[["1"]]))