NC237. 最大矩形
描述
示例1
输入:
[[1]]
输出:
1
示例2
输入:
[[1,1],[0,1]]
输出:
2
说明:
第一列的两个 1 组成一个矩形示例3
输入:
[[0,0],[0,0]]
输出:
0
示例4
输入:
[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]
输出:
8
C++ 解法, 执行用时: 5ms, 内存消耗: 676KB, 提交时间: 2022-02-10
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix int整型vector<vector<>>
* @return int整型
*/
int maximalRectangle(vector<vector<int> >& matrix) {
// write code here
int maxArea = 0;
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(matrix[i][j]){
if(j)
matrix[i][j] = matrix[i][j - 1] + 1;
int len = matrix[i][j];
int height = 1;
while(i - height + 1 >= 0 && matrix[i - height + 1][j]){
len = min(len, matrix[i - height + 1][j]);
maxArea = max(maxArea, len * height);
++height;
}
}
}
}
return maxArea;
}
};
C 解法, 执行用时: 6ms, 内存消耗: 640KB, 提交时间: 2022-06-05
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix int整型二维数组
* @param matrixRowLen int matrix数组行数
* @param matrixColLen int* matrix数组列数
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int max(int a, int b) {
return a > b ? a : b;
}
int largestRectangleArea(int *heights, int cols) {
// 判断height，为空直接返回0
if (cols == 0) {
return 0;
}
int res = 0;
int *h = (int *)malloc(sizeof(int) * (cols + 2));
memcpy(h + 1, heights, sizeof(int) * cols);
h[0] = 0;
h[cols+1] = 0;
int n = cols + 2;
int stack[203] = {0};
int sTop = 0;
int curWidth = 0;
int curHeight = 0;
for (int i = 0; i < n; i++) {
while ((sTop > 0) && (h[i] < h[stack[sTop-1]])) {
if (sTop - 2 >= 0) {
curWidth = i - stack[sTop - 2] - 1;
} else {
curWidth = i;
}
curHeight = h[stack[sTop-1]];
sTop--;
res = max(res, curWidth * curHeight);
}
stack[sTop++] = i;
}
free(h);
return res;
}
int maximalRectangle(int** matrix, int matrixRowLen, int* matrixColLen ) {
// 获取矩阵的长宽
if (matrix == NULL || matrixRowLen == 0) {
return 0;
}
int rows = matrixRowLen;
int cols = *matrixColLen;
int *heights = (int *)malloc(sizeof(int) * cols);
memset(heights, 0, sizeof(int) * cols);
int res = 0;
// 预处理矩阵
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
heights[j] = heights[j] + 1;
} else {
heights[j] = 0;
}
}
res = max(res, largestRectangleArea(heights, cols));
}
free(heights);
return res;
}
C++ 解法, 执行用时: 6ms, 内存消耗: 680KB, 提交时间: 2022-05-03
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix int整型vector<vector<>>
* @return int整型
*/
int largestRectangleArea(vector<int>& heights){
stack<int> s;
s.push(-1);
int ans=0;
for(int i=0;i<heights.size();++i){
while(s.top()!=-1 && heights[i]<=heights[s.top()]){
int index=s.top();
s.pop();
ans=max(ans,heights[index]*(i-s.top()-1));
}
s.push(i);
}
while(s.top()!=-1){
int index=s.top();
s.pop();
ans=max(ans,heights[index]*((int)(heights.size())-s.top()-1));
}
return ans;
}
int maximalRectangle(vector<vector<int> >& matrix) {
// write code here
int m=matrix.size(),n=matrix[0].size();
vector<int> heights(n,0);
int ans=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(matrix[i][j]==1) heights[j]+=1;
else{
heights[j]=0;
}
}
ans=max(ans,largestRectangleArea(heights));
}
return ans;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 692KB, 提交时间: 2022-04-01
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix int整型vector<vector<>>
* @return int整型
*/
int largestRectangle(vector<int>& height) {
int n = height.size();
vector<int> left(n);
vector<int> right(n);
stack<int> monoStack;
int res = 0;
for (int i = 0; i < n; ++i) {
while (!monoStack.empty() && height[i] <= height[monoStack.top()])
monoStack.pop();
left[i] = monoStack.empty() ? -1 : monoStack.top(); //注意！返回的是单调栈的栈顶
monoStack.push(i);
}
monoStack = stack<int>();
for (int i = n - 1; i >= 0; --i) { //注意 i从n-1开始
while (!monoStack.empty() && height[i] <= height[monoStack.top()])
monoStack.pop();
right[i] = monoStack.empty() ? n : monoStack.top(); //注意！返回的是单调栈的栈顶
monoStack.push(i);
}
for (int i = 0; i < n; ++i)
res = max(res, (right[i] - left[i] - 1) * height[i]);
return res;
}
int maximalRectangle(vector<vector<int> >& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> height(n);
int res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 1) //注意 是数字1
height[j]++;
else
height[j] = 0;
}
res = max(res, largestRectangle(height));
}
return res;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 716KB, 提交时间: 2022-01-26
class Solution {
public:
/*
单调栈
*/
int maximalRectangle(vector<vector<int>> &mat) {
int j, mx_h, mx_area;
int n = mat.size();
int m = mat[0].size();
vector<int> h_arr(n, 0);
// 按列构造直方图
for(int i = 0; i < n; i++) {
for(int j = m-2; j >=0; j--) {
mat[i][j] = (mat[i][j] == 1) ? (mat[i][j] + mat[i][j+1]) : 0;
}
}
// 按列开始找最大直方图的矩形面积
j = 0;
mx_area = 0;
while(j < m) {
mx_h = 0;
for(int i = 0; i < n; i++) {
h_arr[i] = mat[i][j];
mx_h = max(mx_h, h_arr[i]);
}
if(mx_h == 0) { // 重要剪枝
j++;
continue;
}
mx_area = max(mx_area, fn_large_area(h_arr));
j++;
}
return mx_area;
}
private:
// 单调栈
int fn_large_area(vector<int> &nums) {
stack<int> stk; // 存放索引
int n = nums.size();
int h, l_idx, mx_area;
mx_area = 0;
for(int i = 0; i < n; i++) {
while(!stk.empty() && nums[i] < nums[stk.top()]) { // 违背单调栈条件时
h = nums[stk.top()]; stk.pop();
l_idx = stk.empty() ? 0 : (stk.top() + 1);
mx_area = max(mx_area, h * (i - l_idx)); // 统计递减矩形最大面积
}
stk.push(i);
}
while(!stk.empty()) { // 单调栈统计矩形最大面积
h = nums[stk.top()]; stk.pop();
l_idx = stk.empty() ? 0 : (stk.top() + 1);
mx_area = max(mx_area, h * (n - l_idx));
}
return mx_area;
}
};