Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

参考84题的单调栈解法

求最大矩形=》求解包含当前柱子的最大矩阵=》就两端第一个小于该柱子的索引位置=>利用单调递增栈 （两端初始化一个0）

单调递减栈可以用来求两端第一个大于该柱子的索引值 （两端初始化一个极大值） 便于后面弹栈

CPP 代码

class Solution {
public:
int maximalRectangle(vector>& matrix) {
// 利用单调栈进行求解
if(matrix.size()==0) return 0;
int m=matrix.size(),n=matrix[0].size();
vector dp(n,0);
int res=0;
for(int i=0;i<m;++i){
dp.resize(matrix[i].size());
for(int j=0;j<n;++j){
if(matrix[i][j]=='0'){
dp[j]=0;
}
else{
dp[j]=dp[j]+1;
}
}
int tmp=calrect(dp);
res=max(res,tmp);
}
return res;

}  
int calrect(vector<int> dp){  
    dp.push\_back(0);  
    dp.insert(dp.begin(),0);  
    stack<int>ss;  
    int n=dp.size();  
    int res=0;  
    for(int i=0;i<n;++i){  
        while(ss.size() && dp\[ss.top()\]>dp\[i\]){  
        int tmp=ss.top();ss.pop();  
        res=max(res,dp\[tmp\]\*(i-ss.top()-1));  
        }  
        ss.push(i);  
    }  
    return res;  
}  

};

Python 代码

class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
#这题如何暴力法求解呢？
#能不能换成柱子 好像不行哎
#利用单调栈
if not matrix:
return 0
m=len(matrix)
n=len(matrix[0])
stack=[0]*n
res=0
for i in range(m):
for j in range(n):
if matrix[i][j]=="0":
stack[j]=0
else:
stack[j]+=1
#启用单调栈来计算当前柱子的最大面积
are=self.calrect(stack)
res=max(are,res)

    return res

def calrect(self,height): #单调栈求最大面积  
    height=\[0\]+height+\[0\]  
    stack=\[\]#维护一个单调递增栈 统计每个柱子两边第一个比他小的柱子  
    n=len(height)  
    res=0  
    for i in range(n):  
        while stack and height\[stack\[-1\]\]>height\[i\]:  
            tmp=stack.pop()  
            are=(i-stack\[-1\]-1)\*height\[tmp\]  
            res=max(res,are)  
        stack.append(i)  
    return res