非递归实现任意柱状图求最大矩形面积c语言
时间: 2023-08-04 15:02:47 浏览: 49
以下是非递归实现任意柱状图求最大矩形面积的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 定义栈结构体
typedef struct {
int top; // 栈顶指针
int* arr; // 存储栈元素的数组
} Stack;
// 创建一个栈
Stack* create(int size) {
Stack* s = (Stack*)malloc(sizeof(Stack));
s->top = -1;
s->arr = (int*)malloc(sizeof(int) * size);
return s;
}
// 判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack* s, int size) {
return s->top == size - 1;
}
// 入栈
void push(Stack* s, int x) {
s->arr[++s->top] = x;
}
// 出栈
int pop(Stack* s) {
return s->arr[s->top--];
}
// 获取栈顶元素
int peek(Stack* s) {
return s->arr[s->top];
}
// 求最大矩形面积
int largestRectangleArea(int* heights, int heightsSize) {
Stack* s = create(heightsSize + 1); // 创建栈,栈的大小为 heightsSize + 1
int maxArea = 0; // 最大矩形面积
int i = 0; // 遍历 heights 数组的指针
while (i < heightsSize || !isEmpty(s)) {
if (isEmpty(s) || heights[i] >= heights[peek(s)]) {
push(s, i++); // 如果栈为空或当前元素大于等于栈顶元素,将当前元素入栈
} else {
int top = pop(s); // 如果当前元素小于栈顶元素,弹出栈顶元素
int width = isEmpty(s) ? i : i - peek(s) - 1; // 计算矩形宽度
int area = heights[top] * width; // 计算矩形面积
if (area > maxArea) {
maxArea = area; // 更新最大矩形面积
}
}
}
// 释放栈占用的内存
free(s->arr);
free(s);
return maxArea;
}
// 求矩阵中最大矩形面积
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
if (matrixSize == 0 || matrixColSize == NULL || matrixColSize[0] == 0) {
return 0;
}
int n = matrixColSize[0]; // 矩阵的列数
int* heights = (int*)malloc(sizeof(int) * n); // 存储每一行的高度
int maxArea = 0; // 最大矩形面积
for (int i = 0; i < matrixSize; i++) {
// 计算当前行的高度
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
heights[j] = 0;
} else {
heights[j]++;
}
}
// 计算以当前行为底边的最大矩形面积
int area = largestRectangleArea(heights, n);
if (area > maxArea) {
maxArea = area; // 更新最大矩形面积
}
}
// 释放 heights 数组占用的内存
free(heights);
return maxArea;
}
int main() {
char* matrix[] = {"10100", "10111", "11111", "10010"};
int matrixSize = sizeof(matrix) / sizeof(char*);
int matrixColSize[] = {5, 5, 5, 5};
int maxArea = maximalRectangle(matrix, matrixSize, matrixColSize);
printf("最大矩形面积:%d\n", maxArea);
return 0;
}
```
该算法的时间复杂度为O(mn),空间复杂度为O(n),其中m为矩阵的行数,n为矩阵的列数。
相关推荐
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)