leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

maximal_rectangle.c (1954B)

 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 85. Maximal Rectangle
#include "leetcode.h"

/*
 * 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.
 */

int maximalRectangle(char **matrix, int matrixSize, int *matrixColSize) {
  if (!matrixSize || !*matrixColSize)
    return 0;
  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]);
  }
  free(height);
  free(left);
  free(right);
  return ans;
}

int main() {
  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
}