输出一个矩阵中,由1组成的最大矩形面积,手动输入矩阵C++
时间: 2023-07-16 14:15:46 浏览: 99
以下是C++代码:
```cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int maximalRectangle(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
vector<int> heights(n, 0);
int maxArea = 0;
for (int i = 0; i < m; i++) {
// update the heights array for each row
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
heights[j] = 0;
} else {
heights[j]++;
}
}
// calculate the max area for this row
stack<int> stk;
for (int j = 0; j <= n; j++) {
while (!stk.empty() && (j == n || heights[stk.top()] > heights[j])) {
int h = heights[stk.top()];
stk.pop();
int w = stk.empty() ? j : j - stk.top() - 1;
maxArea = max(maxArea, h * w);
}
stk.push(j);
}
}
return maxArea;
}
int main() {
vector<vector<int>> matrix;
matrix.push_back({1, 0, 1, 0, 0});
matrix.push_back({1, 0, 1, 1, 1});
matrix.push_back({1, 1, 1, 1, 1});
matrix.push_back({1, 0, 0, 1, 0});
int area = maximalRectangle(matrix);
cout << "The maximum rectangle area is: " << area << endl;
return 0;
}
```
这个算法的时间复杂度为O(mn),其中m和n分别是矩阵的行数和列数。
阅读全文