gitschaub · April 10, 2019 14:36
diff --git a/leetcode_85_maximal-rectangle_stack.c b/leetcode_85_maximal-rectangle_stack.c
 const int STACK_CAP_DEFAULT = 10;

 typedef struct {
    int *data;
    int len;
    int cap;
 } Stack;

 Stack *Stack_init() {
    Stack *stk = malloc(sizeof(Stack));
    stk->len = 0;
    stk->cap = STACK_CAP_DEFAULT;
    stk->data = malloc(stk->cap * sizeof(int));
    
    return stk;
 }

 void Stack_push(Stack *stk, int v) {
    if(stk->len == stk->cap) {
        // grow stack
        int n_cap = stk->cap * 2;
        stk->data = realloc(stk->data, stk->cap * sizeof(int));
    }
    // Append element
    stk->data[stk->len] = v;
    stk->len++;
 }

 bool Stack_empty(Stack *stk) {
    return stk->len == 0;
 }

 int Stack_peek(Stack *stk) {
    if(Stack_empty(stk)) return -1;
    return stk->data[stk->len-1];
 }

 int Stack_pop(Stack *stk) {
    if(Stack_empty(stk)) return -1;
    int top = stk->data[stk->len-1];
    stk->len -= 1;
    return top;
 }

 void Stack_free(Stack *stk) {
    free(stk->data);
    free(stk);
 }

 int **make_dp_mat(int rowSize, int colSize) {
     int **dp = (int **)malloc(rowSize * sizeof(int *));
    for(int i = 0; i < rowSize; i++){
        dp[i] = (int *)malloc(colSize * sizeof(int));
        memset(dp[i], 0, colSize * sizeof(int));
    }
        
    return dp;   
 }

 int max_int(int a, int b) {
    return a > b ? a : b;
 }

 // Determine the largest rectangle that can be formed
 // from contiguous 1's on a single row
 int max_rect_row(int *heights, int len) {
    if(len == 0) {
        return 0;
    }
    
    // For each column and direction (left/right), 
    // determine the index of the last column with
    // height >= the starting column
    int dp_left[len];
    dp_left[0] = -1;
    
    // Stack tracks indices of columns with height
    // less than 
    Stack *stk = Stack_init();
    Stack_push(stk, 0);
    for(int i = 1; i < len; i++) {
        int h = heights[i];
        // For current position, drain indices of all
        // columns with equal or greater height than
        // current
        while(!Stack_empty(stk) &&
              heights[Stack_peek(stk)] >= h) {
            Stack_pop(stk);
        }
        
        // Leftover indices on stack mark first column
        // with height < column height
        if(!Stack_empty(stk)) {
            dp_left[i] = Stack_peek(stk);
        } else {
            dp_left[i] = -1;
        }
        
        Stack_push(stk, i);
    }
    
    
    int dp_right[len];
    dp_right[len-1] = len;
    Stack_free(stk);
    stk = Stack_init();
    Stack_push(stk, len-1);
    for(int i = len-2; i >= 0; i--) {
        int h = heights[i];
        
        while(!Stack_empty(stk) &&
             heights[Stack_peek(stk)] >= h) {
            Stack_pop(stk);
        }
        
        if(!Stack_empty(stk)) {
            dp_right[i] = Stack_peek(stk);
        } else {
            dp_right[i] = len;
        }
        
        Stack_push(stk, i);
    }
    
    for(int i = len-1; i >= 0; i--) {
        int h = heights[i];
        int j = i-1;
        for(; j >= 0; j--) {
            if(heights[j] < h) break;
        }
        dp_left[i] = j;
    }
    
    // Calculate max rect area for each column
    int max = 0; 
    for(int i = 0; i < len; i++) {
        int left_dist = i - dp_left[i];
        int right_dist = dp_right[i] - i;
        max = max_int(max, heights[i] * (left_dist+right_dist-1));
    }
    
    Stack_free(stk);
    return max;
 }

 int maximalRectangle(char** matrix, int matrixRowSize, int *matrixColSizes) {
    // Initialize an RxC Rect matrix and set elements to 0 
    if(matrixRowSize == 0) return 0;
    if((int)matrixColSizes == 0) return 0;
    int colSize = (int)matrixColSizes;
    int rowSize = matrixRowSize;
    int **dp = make_dp_mat(rowSize, colSize);

    // For each col in each row, calculate the number
    // of contiguous 1's above the column
    for(int c = 0; c < colSize; c++) {
        dp[0][c] = matrix[0][c] - '0';
    }
    for(int r = 1; r < rowSize; r++) {
        int p = r-1;
        for(int c = 0; c < colSize; c++) {
            if(matrix[r][c] == '0') {
                dp[r][c] = 0;
                continue;
            }
            dp[r][c] = dp[p][c] + 1;
        }
    }
    
    int max = 0;
    for(int r = 0; r < rowSize; r++) {
        max = max_int(max, max_rect_row(dp[r], colSize));
    }
    
    return max;
 }
	const int STACK_CAP_DEFAULT = 10;

	typedef struct {
	int *data;
	int len;
	int cap;
	} Stack;

	Stack *Stack_init() {
	Stack *stk = malloc(sizeof(Stack));
	stk->len = 0;
	stk->cap = STACK_CAP_DEFAULT;
	stk->data = malloc(stk->cap * sizeof(int));

	return stk;
	}

	void Stack_push(Stack *stk, int v) {
	if(stk->len == stk->cap) {
	// grow stack
	int n_cap = stk->cap * 2;
	stk->data = realloc(stk->data, stk->cap * sizeof(int));
	}
	// Append element
	stk->data[stk->len] = v;
	stk->len++;
	}

	bool Stack_empty(Stack *stk) {
	return stk->len == 0;
	}

	int Stack_peek(Stack *stk) {
	if(Stack_empty(stk)) return -1;
	return stk->data[stk->len-1];
	}

	int Stack_pop(Stack *stk) {
	if(Stack_empty(stk)) return -1;
	int top = stk->data[stk->len-1];
	stk->len -= 1;
	return top;
	}

	void Stack_free(Stack *stk) {
	free(stk->data);
	free(stk);
	}

	int **make_dp_mat(int rowSize, int colSize) {
	int dp = (int )malloc(rowSize * sizeof(int *));
	for(int i = 0; i < rowSize; i++){
	dp[i] = (int )malloc(colSize sizeof(int));
	memset(dp[i], 0, colSize * sizeof(int));
	}

	return dp;
	}

	int max_int(int a, int b) {
	return a > b ? a : b;
	}

	// Determine the largest rectangle that can be formed
	// from contiguous 1's on a single row
	int max_rect_row(int *heights, int len) {
	if(len == 0) {
	return 0;
	}

	// For each column and direction (left/right),
	// determine the index of the last column with
	// height >= the starting column
	int dp_left[len];
	dp_left[0] = -1;

	// Stack tracks indices of columns with height
	// less than
	Stack *stk = Stack_init();
	Stack_push(stk, 0);
	for(int i = 1; i < len; i++) {
	int h = heights[i];
	// For current position, drain indices of all
	// columns with equal or greater height than
	// current
	while(!Stack_empty(stk) &&
	heights[Stack_peek(stk)] >= h) {
	Stack_pop(stk);
	}

	// Leftover indices on stack mark first column
	// with height < column height
	if(!Stack_empty(stk)) {
	dp_left[i] = Stack_peek(stk);
	} else {
	dp_left[i] = -1;
	}

	Stack_push(stk, i);
	}


	int dp_right[len];
	dp_right[len-1] = len;
	Stack_free(stk);
	stk = Stack_init();
	Stack_push(stk, len-1);
	for(int i = len-2; i >= 0; i--) {
	int h = heights[i];

	while(!Stack_empty(stk) &&
	heights[Stack_peek(stk)] >= h) {
	Stack_pop(stk);
	}

	if(!Stack_empty(stk)) {
	dp_right[i] = Stack_peek(stk);
	} else {
	dp_right[i] = len;
	}

	Stack_push(stk, i);
	}

	for(int i = len-1; i >= 0; i--) {
	int h = heights[i];
	int j = i-1;
	for(; j >= 0; j--) {
	if(heights[j] < h) break;
	}
	dp_left[i] = j;
	}

	// Calculate max rect area for each column
	int max = 0;
	for(int i = 0; i < len; i++) {
	int left_dist = i - dp_left[i];
	int right_dist = dp_right[i] - i;
	max = max_int(max, heights[i] * (left_dist+right_dist-1));
	}

	Stack_free(stk);
	return max;
	}

	int maximalRectangle(char** matrix, int matrixRowSize, int *matrixColSizes) {
	// Initialize an RxC Rect matrix and set elements to 0
	if(matrixRowSize == 0) return 0;
	if((int)matrixColSizes == 0) return 0;
	int colSize = (int)matrixColSizes;
	int rowSize = matrixRowSize;
	int **dp = make_dp_mat(rowSize, colSize);

	// For each col in each row, calculate the number
	// of contiguous 1's above the column
	for(int c = 0; c < colSize; c++) {
	dp[0][c] = matrix[0][c] - '0';
	}
	for(int r = 1; r < rowSize; r++) {
	int p = r-1;
	for(int c = 0; c < colSize; c++) {
	if(matrix[r][c] == '0') {
	dp[r][c] = 0;
	continue;
	}
	dp[r][c] = dp[p][c] + 1;
	}
	}

	int max = 0;
	for(int r = 0; r < rowSize; r++) {
	max = max_int(max, max_rect_row(dp[r], colSize));
	}

	return max;
	}