LeetCode 0085 - Maximal Rectangle
# Hints
- 单调栈
# 前置题目
LeetCode 0084 - Largest Rectangle in Histogram
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
# 题意
给定一个 的 矩阵,求其最大全 子矩阵的面积。
# 题解
考虑枚举子矩阵的底部一行的行号,问题即可转化为求 次 LeetCode 0084 的直方图最大矩形问题,总的时间复杂度为 。
代码实现将子问题分离为两个函数,多次进行运行时刻内存分配导致时间效率稍低,将两个函数耦合到一起即可提高效率。
# AC代码
class Solution {
public:
int maximalRectangle(vector<vector<char>> & matrix) {
// 特判
if (matrix.empty() || matrix.front().empty()) {
return 0;
}
// 初始化
int m = matrix.size(), n = matrix.front().size();
// 遍历
int res = 0;
vector<int> heights(n, 0);
for (int i = 0; i < m; i ++) {
// 计算高度
for (int j = 0; j < n; j ++) {
int x = (matrix[i][j] - '0');
if (x == 0) {
heights[j] = 0;
} else {
heights[j] += x;
}
}
// 更新答案
res = max(res, largestRectangleArea(heights));
}
// 返回
return res;
}
// 直方图最大矩形
int largestRectangleArea(vector<int> & heights) {
// 初始化
heights.push_back(-1);
int n = heights.size();
vector<int> lefts(n), rights(n);
// 主循环
stack<int> s;
for (int i = 0; i < n; i ++) {
// 出栈
while (!s.empty() && heights[s.top()] > heights[i]) {
rights[s.top()] = i - 1;
s.pop();
}
// 入栈
lefts[i] = (s.empty() ? 0 : s.top() + 1);
s.push(i);
}
// 求最大值
int res = 0;
for (int i = 0; i < n - 1; i ++) {
int area = (rights[i] - lefts[i] + 1) * heights[i];
res = max(res, area);
}
// 返回
heights.pop_back();
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01