SHARE
TWEET

Untitled

a guest Apr 20th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int STACK_CAP_DEFAULT = 10;
  2.  
  3. typedef struct {
  4.     int *data;
  5.     int len;
  6.     int cap;
  7. } Stack;
  8.  
  9. Stack *Stack_init() {
  10.     Stack *stk = malloc(sizeof(Stack));
  11.     stk->len = 0;
  12.     stk->cap = STACK_CAP_DEFAULT;
  13.     stk->data = malloc(stk->cap * sizeof(int));
  14.    
  15.     return stk;
  16. }
  17.  
  18. void Stack_push(Stack *stk, int v) {
  19.     if(stk->len == stk->cap) {
  20.         // grow stack
  21.         int n_cap = stk->cap * 2;
  22.         stk->data = realloc(stk->data, stk->cap * sizeof(int));
  23.     }
  24.     // Append element
  25.     stk->data[stk->len] = v;
  26.     stk->len++;
  27. }
  28.  
  29. bool Stack_empty(Stack *stk) {
  30.     return stk->len == 0;
  31. }
  32.  
  33. int Stack_peek(Stack *stk) {
  34.     if(Stack_empty(stk)) return -1;
  35.     return stk->data[stk->len-1];
  36. }
  37.  
  38. int Stack_pop(Stack *stk) {
  39.     if(Stack_empty(stk)) return -1;
  40.     int top = stk->data[stk->len-1];
  41.     stk->len -= 1;
  42.     return top;
  43. }
  44.  
  45. void Stack_free(Stack *stk) {
  46.     free(stk->data);
  47.     free(stk);
  48. }
  49.  
  50. int **make_dp_mat(int rowSize, int colSize) {
  51.      int **dp = (int **)malloc(rowSize * sizeof(int *));
  52.     for(int i = 0; i < rowSize; i++){
  53.         dp[i] = (int *)malloc(colSize * sizeof(int));
  54.         memset(dp[i], 0, colSize * sizeof(int));
  55.     }
  56.        
  57.     return dp;  
  58. }
  59.  
  60. int max_int(int a, int b) {
  61.     return a > b ? a : b;
  62. }
  63.  
  64. // Determine the largest rectangle that can be formed
  65. // from contiguous 1's on a single row
  66. int max_rect_row(int *heights, int len) {
  67.     if(len == 0) {
  68.         return 0;
  69.     }
  70.    
  71.     // For each column and direction (left/right),
  72.     // determine the index of the last column with
  73.     // height >= the starting column
  74.     int dp_left[len];
  75.     dp_left[0] = -1;
  76.    
  77.     // Stack tracks indices of columns with height
  78.     // less than
  79.     Stack *stk = Stack_init();
  80.     Stack_push(stk, 0);
  81.     for(int i = 1; i < len; i++) {
  82.         int h = heights[i];
  83.         // For current position, drain indices of all
  84.         // columns with equal or greater height than
  85.         // current
  86.         while(!Stack_empty(stk) &&
  87.               heights[Stack_peek(stk)] >= h) {
  88.             Stack_pop(stk);
  89.         }
  90.        
  91.         // Leftover indices on stack mark first column
  92.         // with height < column height
  93.         if(!Stack_empty(stk)) {
  94.             dp_left[i] = Stack_peek(stk);
  95.         } else {
  96.             dp_left[i] = -1;
  97.         }
  98.        
  99.         Stack_push(stk, i);
  100.     }
  101.    
  102.    
  103.     int dp_right[len];
  104.     dp_right[len-1] = len;
  105.     Stack_free(stk);
  106.     stk = Stack_init();
  107.     Stack_push(stk, len-1);
  108.     for(int i = len-2; i >= 0; i--) {
  109.         int h = heights[i];
  110.        
  111.         while(!Stack_empty(stk) &&
  112.              heights[Stack_peek(stk)] >= h) {
  113.             Stack_pop(stk);
  114.         }
  115.        
  116.         if(!Stack_empty(stk)) {
  117.             dp_right[i] = Stack_peek(stk);
  118.         } else {
  119.             dp_right[i] = len;
  120.         }
  121.        
  122.         Stack_push(stk, i);
  123.     }
  124.    
  125.     for(int i = len-1; i >= 0; i--) {
  126.         int h = heights[i];
  127.         int j = i-1;
  128.         for(; j >= 0; j--) {
  129.             if(heights[j] < h) break;
  130.         }
  131.         dp_left[i] = j;
  132.     }
  133.    
  134.     // Calculate max rect area for each column
  135.     int max = 0;
  136.     for(int i = 0; i < len; i++) {
  137.         int left_dist = i - dp_left[i];
  138.         int right_dist = dp_right[i] - i;
  139.         max = max_int(max, heights[i] * (left_dist+right_dist-1));
  140.     }
  141.    
  142.     Stack_free(stk);
  143.     return max;
  144. }
  145.  
  146. int maximalRectangle(char** matrix, int matrixRowSize, int *matrixColSizes) {
  147.     // Initialize an RxC Rect matrix and set elements to 0
  148.     if(matrixRowSize == 0) return 0;
  149.     if((int)matrixColSizes == 0) return 0;
  150.     int colSize = (int)matrixColSizes;
  151.     int rowSize = matrixRowSize;
  152.     int **dp = make_dp_mat(rowSize, colSize);
  153.  
  154.     // For each col in each row, calculate the number
  155.     // of contiguous 1's above the column
  156.     for(int c = 0; c < colSize; c++) {
  157.         dp[0][c] = matrix[0][c] - '0';
  158.     }
  159.     for(int r = 1; r < rowSize; r++) {
  160.         int p = r-1;
  161.         for(int c = 0; c < colSize; c++) {
  162.             if(matrix[r][c] == '0') {
  163.                 dp[r][c] = 0;
  164.                 continue;
  165.             }
  166.             dp[r][c] = dp[p][c] + 1;
  167.         }
  168.     }
  169.    
  170.     int max = 0;
  171.     for(int r = 0; r < rowSize; r++) {
  172.         max = max_int(max, max_rect_row(dp[r], colSize));
  173.     }
  174.    
  175.     return max;
  176. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top