【leetcode刷题】T23-最大矩形
【英文题目】（学习英语的同时，更能理解题意哟~）
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:
【中文题目】
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出:
【思路】
如果明白【T22-柱状图中最大的矩形】这道题的思路，那么本题的想法就很自然了：对于每一行，将其转换为柱状图，计算最大矩形面积即可。时间复杂度为O(n^2)。
（柱状图中计算矩形面积，需要使用一个栈，栈顶到栈底元素从大到小，这样每遇到一个比栈顶元素小的元素，则弹出栈，计算矩形面积，返回面积最大值即可。）
本题还可以使用动态规划来完成，待以后刷题时再来解决。
【代码】
python版本
class Solution(object):
def update(self, ls, matrix, i):
for j, m in enumerate(matrix[i]):
ls[j] = ls[j] + if m == '1' else
return ls
def cal_value(self, heights):
heights.append(-1)
stack = []
res =
for i, h in enumerate(heights):
while(len(stack) > and h <= heights[stack[-1]]):
a = heights[stack.pop()]
j = stack[-1] if len(stack) > else -1
# print(a, i-j-1)
res = max(res, a * (i-j-1))
stack.append(i)
return res
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if len(matrix) == or len(matrix[]) == :
return
ls = [] * len(matrix[])
res =
# 对于每一行
for i in range(len(matrix)):
# 更新ls，并计算最大矩形
ls = self.update(ls, matrix, i)
res = max(res, self.cal_value(ls))
return res
C++版本
class Solution {
public:
int cal_value(vector<int> heights){
stack<int> ls;
int res = ;
heights.push_back(-1);
for(int i=; i < heights.size(); i++){
while(ls.size() > && heights[i] <= heights[ls.top()]){
int a = heights[ls.top()];
ls.pop();
int j = -1;
if(ls.size() > )
j = ls.top();
if(res < a * (i - j - ))
res = a * (i - j - );
}
ls.push(i);
}
return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == or matrix[].size() == )
return ;
vector<int> ls(matrix[].size(), );
int res = ;
// 每行转换为柱状图，计算最大面积
for(int i=; i < matrix.size(); i++){
for(int j=; j < matrix[].size(); j++){
if(matrix[i][j] == '0')
ls[j] = ;
else
ls[j]++;
}
res = max(res, cal_value(ls));
}
return res;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读