最大矩形
题目 Maximal Rectangle
思路分析
将二维矩阵拆分成一行一行
问题转换为 直方图中最大的矩形
在这里用数组模拟 N不能在编译时确定
所以要用到new操作 所以反倒是比直接stl vector慢
代码实现
模拟单调栈 33ms
class Solution {
public:
// 计算直方图中最大矩形的面积
int histMaximalRectangle(const vector<int>& heights) {
int n = heights.size();
int* h = new int[n + 2];// 动态数组以容纳哨兵值
h[0] = -1;
h[n + 1] = -1;
for (int i = 0; i < n; ++i) {
h[i + 1] = heights[i];
}
int* l = new int[n + 2];
int* r = new int[n + 2];
int* s = new int[n + 2];
int top = 0;
s[0]=0;
for(int i=1;i<=n;i++){
while(h[s[top]]>=h[i])
top--;
l[i]=s[top];
s[++top]=i;
}
top=0;
s[0]=n+1;
for(int i=n;i>=1;i--){
while(h[s[top]]>=h[i])
top--;
r[i]=s[top];
s[++top]=i;
}
int max_area = 0;
for (int i = 1; i <= n; ++i) {
max_area = max(max_area, h[i] * ((r[i]-1)-(l[i]+1)+1));
}
delete[] h;
delete[] l;
delete[] r;
delete[] s;
return max_area;
}
int maximalRectangle(vector<vector<char>>& matrix) {
// 检查矩阵是否为空
if (matrix.empty())
return 0;
int rowN = matrix.size();// 矩阵的行数
int colN = matrix[0].size();// 矩阵的列数
// 如果行数或列数为0，则返回0
if (rowN == 0 || colN == 0)
return 0;
// 存储每行的直方图
vector<vector<int>> hist_matrix(rowN, vector<int>(colN, 0));
int max_area = 0;// 最大面积
// 构建每一行的直方图
for (int i = 0; i < rowN; ++i) {
for (int j = 0; j < colN; ++j) {
if (matrix[i][j] == '1') {
hist_matrix[i][j] = 1;// 当前元素为'1'
if (i - 1 >= 0) {// 如果不是第一行，累加上方的值
hist_matrix[i][j] += hist_matrix[i-1][j];
}
}
}
}
for (int i = 0; i < rowN; ++i) {
max_area = max(max_area, histMaximalRectangle(hist_matrix[i]));
}
return max_area;
}
};
stl 27ms
class Solution {
public:
// 计算直方图中最大矩形的面积
int histMaximalRectangle(const vector<vector<int>>& matrix, int row_idx) {
stack<int> stack; // 用于存储索引的栈
int max_area = 0; // 最大面积
vector<int> row = matrix[row_idx]; // 当前行的直方图
row.push_back(0); // 添加哨兵以简化处理
for (int i = 0; i < row.size(); ++i) {
int curr = row[i];
// 当栈非空且当前元素小于栈顶元素对应的高度时
while (!stack.empty() && row[stack.top()] > curr) {
int top = stack.top(); // 获取栈顶元素
stack.pop(); // 弹出栈顶元素
int left = stack.empty() ? 0 : stack.top() + 1; // 计算左边界
int right = i - 1; // 计算右边界
// 更新最大面积
max_area = max(max_area, (right - left + 1) * row[top]);
}
stack.push(i); // 将当前索引压入栈
}
return max_area; // 返回最大面积
}
int maximalRectangle(vector<vector<char>>& matrix) {
// 检查矩阵是否为空
if (matrix.empty())
return 0;
int rowN = matrix.size();// 矩阵的行数
int colN = matrix[0].size();// 矩阵的列数
// 如果行数或列数为0，则返回0
if (rowN == 0 || colN == 0)
return 0;
// 存储每行的直方图
vector<vector<int>> hist_matrix(rowN, vector<int>(colN, 0));
int max_area = 0;// 最大面积
// 构建每一行的直方图
for (int i = 0; i < rowN; ++i) {
for (int j = 0; j < colN; ++j) {
if (matrix[i][j] == '1') {
hist_matrix[i][j] = 1;// 当前元素为'1'
if (i - 1 >= 0) {// 如果不是第一行，累加上方的值
hist_matrix[i][j] += hist_matrix[i-1][j];
}
}
}
// 计算当前行直方图中最大的矩形面积
int row_max_area = histMaximalRectangle(hist_matrix, i);
// 更新全局最大面积
max_area = max(row_max_area, max_area);
}
return max_area;
}
};
💬 评论