[题目][栈] 最大矩形
咱们继续，再来个最大矩形。
不同于 柱状图的最大矩形，这次计算的是一个矩阵，而矩阵是由一行一行数据组成的，就意味着其是多个相同个数的柱状图组成的，以案例为例：
## 矩阵 [0] 1 0 1 0 0 [1] 1 0 1 1 1 [2] 1 1 1 1 1 [3] 1 0 0 1 0 ## [0] 1 0 1 0 0 对应柱形 1 0 1 0 0 ## [1] 1 0 1 1 1 对应柱形 2 0 2 0 0 1 0 1 1 1 ## [2] 1 1 1 1 1 对应柱形 3 0 3 0 0 2 0 2 2 2 1 1 1 1 1 ## [3] 1 0 0 1 0 对应柱形 4 0 3 0 3 2 2 1 0 0 1 0
则我们可以遍历矩阵的每一行，计算其对应的矩形，剩下的交给求柱形的最大矩形函数中计算。
因此我们需要解决问题只有如何去计算矩阵单行对应的矩形，而上面的方式我们已经说明了如何去计算：
- 记录[0]的对应数据，第一个柱状图实现；
- 接下来到[1]，使用第一个柱状图，如果本行为0则无柱状图出现，如果本行为1则可以对应之前的高度+1；
- 后续均如此
依照这个规则我们写成代码：
// 柱状图的柱形个数
auto size = matrix[0].size();
// 存储矩形 并初始化
vector<int> heights(size, 0);
// 结果
int res{0};
// 遍历一层矩形
for (const auto &row : matrix) {
// 遍历第二层矩形
for (size_t i{0}; i<size; ++i) {
// 获取矩形的高度
// 当前的指向 数字
int cur = row[i] - '0';
switch (cur) {
case 0:
heights[i] = 0;
break;
case 1:
heights[i] += 1;
break;
default:
break;
}
}
// 获取完成
// 其他操作
} 每一次第二层循环都会确定一层的柱状图，根据这个柱状图可以使用之前的思路实现最大面积计算，回忆一下前面的代码，柱状图的最大矩形：
int maxArea(vector<int>& heights) {
// 获取柱形个数
auto size = heights.size();
// 存储边界
stack<int> stk;
// 结果
int res{0};
for (size_t i{0}; i<size; ++i) {
int cur = heights[i];
// 若栈中无元素
if (stk.empty()) {
stk.push(i);
continue;
}
int top_i = stk.top(); // 栈顶索引
int top = heights[top_i]; // 栈顶对应元素
// 触发计算边界
while (!stk.empty() && cur < top) {
// 弹出栈顶
stk.pop();
int left = stk.empty() ? 0 : stk.top() + 1;
int right = i-1;
int width = right-left+1;
// 计算面积
int area = width*top;
// 获取最大
res = max(res, area);
// 下一个条件
top_i = stk.empty() ? 0 : stk.top();
top = heights[top_i];
}
// 完成计算
stk.push(i);
}
// 栈不空
while(!stk.empty()) {
int top_i = stk.top();
stk.pop();
int top = heights[top_i];
int left = stk.empty() ? 0 : stk.top() + 1;
int right = size-1;
int width = right - left + 1;
int area = width*top;
res = max(res, area);
}
// 计算完了
return res;
} 完成这个函数之后，就可以写入整体代码了：
class Solution {
public:
int maxArea(vector<int>& heights) {
// 获取柱形个数
auto size = heights.size();
// 存储边界
stack<int> stk;
// 结果
int res{0};
for (size_t i{0}; i<size; ++i) {
int cur = heights[i];
// 若栈中无元素
if (stk.empty()) {
stk.push(i);
continue;
}
int top_i = stk.top(); // 栈顶索引
int top = heights[top_i]; // 栈顶对应元素
// 触发计算边界
while (!stk.empty() && cur < top) {
// 弹出栈顶
stk.pop();
int left = stk.empty() ? 0 : stk.top() + 1;
int right = i-1;
int width = right-left+1;
// 计算面积
int area = width*top;
// 获取最大
res = max(res, area);
// 下一个条件
top_i = stk.empty() ? 0 : stk.top();
top = heights[top_i];
}
// 完成计算
stk.push(i);
}
// 栈不空
while(!stk.empty()) {
int top_i = stk.top();
stk.pop();
int top = heights[top_i];
int left = stk.empty() ? 0 : stk.top() + 1;
int right = size-1;
int width = right - left + 1;
int area = width*top;
res = max(res, area);
}
// 计算完了
return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if (0 == matrix.size()) {
return 0;
}
// 柱状图的柱形个数
auto size = matrix[0].size();
// 存储矩形 并初始化
vector<int> heights(size, 0);
// 结果
int res{0};
// 遍历一层矩形
for (const auto &row : matrix) {
// 遍历第二层矩形
for (size_t i{0}; i<size; ++i) {
// 获取矩形的高度
// 当前的指向 数字
int cur = row[i] - '0';
switch (cur) {
case 0:
heights[i] = 0;
break;
case 1:
heights[i] += 1;
break;
default:
break;
}
}
// 获取完成
// 其他操作
res = max(res, maxArea(heights));
}
return res;
}
}; 执行用时：52 ms, 在所有 C++ 提交中击败了94.39% 的用户 内存消耗：12.1 MB, 在所有 C++ 提交中击败了44.37% 的用户
还行，时间复杂度为O(M*N)，即取决于矩阵的大小。不过有其他方法吗？
不过这已经是比较简便的思路了，无论如何做，都需要将矩阵遍历一遍，因此时间复杂度无法再降低了。
可以尝试将柱状图的方法融合进代码，实现代码的精简，在一些细节上可以降低些运行时间，但具体就不做了。
（还有动态规划，但本处确保使用栈）
如有错误，欢迎指正！
如有不懂，欢迎讨论！
感谢🙏🏻️观看！
查看3道真题和解析
国家电网稳定性 57人发布
