Maximal Rectangle
问题描述 【LeetCode|85.最大矩阵】Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
参考答案
class Solution {
public:
int maximalRectangle(vector > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0);
fill_n(right,n,n);
fill_n(height,n,0);
int maxA = 0;
for(int i=0;
i=0;
j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n;
cur_right=j;
}
}
// compute the area of rectangle (can do this from either side)
for(int j=0;
j 性能：
文章图片
推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题