第一行输入两个整数 n 和 m,代表 n*m 的矩阵
接下来输入一个 n*m 的矩阵
输出其中全是 1 的所有矩形区域中,最大的矩形区域里 1 的数量。
1 4 1 1 1 0
3
最大的矩形区域有3个1,所以返回3
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX(a, b) ((a) > (b) ? (a) : (b)) typedef struct { int *data; int top; } stack; void init_stack(stack *stp, int *arr); void push(stack *stp, int val); int pop(stack *stp); int peek(stack *stp); bool is_empty(stack *stp); int max_area(const int *height, int n) { int i, j, curArea, maxArea = 0, *data; stack st = {0}, *stp = &st; data = (int *) malloc(n * sizeof(int)); init_stack(stp, data); for (i = 0; i < n; i++) { while (!is_empty(stp) && height[i] < height[peek(stp)]) { j = pop(stp); curArea = height[j] * (i - (is_empty(stp) ? -1 : peek(stp)) - 1); maxArea = MAX(maxArea, curArea); } push(stp, i); } while (!is_empty(stp)) { j = pop(stp); curArea = height[j] * (n - (is_empty(stp) ? -1 : peek(stp)) - 1); maxArea = MAX(maxArea, curArea); } free(data); return maxArea; } int main(void) { int n, m, *height, i, j, tmp, res = 0; scanf("%d%d", &n, &m); height = (int *) calloc(m, sizeof(int)); for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { scanf("%d", &tmp); height[j] = tmp == 0 ? 0 : (height[j] + 1); } tmp = max_area(height, m); res = MAX(res, tmp); } printf("%d\n", res); free(height); return 0; } void init_stack(stack *stp, int *arr) { stp->data = arr; stp->top = -1; } void push(stack *stp, int val) { stp->data[++stp->top] = val; } int pop(stack *stp) { return stp->data[stp->top--]; } int peek(stack *stp) { return stp->data[stp->top]; } bool is_empty(stack *stp) { return stp->top == -1; }