题目描述：
顾名思义，给定n*m大小的01矩阵，要求找到1数量最多的全1子矩阵
题目链接：
85. Maximal Rectangle
问题降阶：
思考二维问题前，先将问题降阶，思考该问题在一维状况下的解决方式会是一个比较好的思路。
题目链接：
485. Max Consecutive Ones
题意：
在01数组中寻找最长连续1的长度
思路：
简单的dp，维护数组中每个位置作为结尾的最长连续1长度。
代码：
/*
Author Owen_Q
*/
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int re = 0;
int now = 0;
for(int i:nums)
{
if(i==1)
{
now+=1;
re = max(re,now);
}
else
now = 0;
}
return re;
}
};
一维转二维：
思路：
解决了一维的问题，对于二维问题，完全可以率先按行进行预处理，处理完后矩阵中存储的即使改行到当前位置为止的最长连续1长度。
而为了寻找最大全1矩阵，完全可以遍历每个位置，以预处理的长度作为第一行，分别向上下下找到第一个小于该长度的行，中间的所有行即可用于形成全1矩阵。于是整理复杂度为
代码：
/*
Author Owen_Q
*/
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n,m;
n = matrix.size();
if(n==0)
return 0;
m = matrix[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
matrix[i][j] -= '0';
if(j>0&&matrix[i][j]>0)
matrix[i][j] += matrix[i][j-1];
cout << (int)matrix[i][j] << " ";
}
cout << endl;
}
int re = 0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int pos0 = i-1;
while(pos0>=0&&matrix[pos0][j]>=matrix[i][j])
pos0--;
int pos1 = i+1;
while(pos1<n&&matrix[pos1][j]>=matrix[i][j])
pos1++;
re = max(re,matrix[i][j]*(pos1-pos0-1));
}
}
return re;
}
};
单调栈优化：
思路：
看到寻找下一个长度更短的行，立刻想到单调栈优化，即可将复杂度降到
至于具体优化策略，则需要整体思路的转化。
相较于原来向上下分别寻找，这次只需要向下维护一个单调栈，每次当元素出栈时，即可利用出栈的行长构造一个全1矩阵。最后将栈清空即可得到最优结果。
构造时以出栈元素为横向边长，以目前栈顶到当前元素的距离为纵向边长即可完成
代码：
/*
Author Owen_Q
*/
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n,m;
n = matrix.size();
if(n==0)
return 0;
m = matrix[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
matrix[i][j] -= '0';
if(j>0&&matrix[i][j]>0)
matrix[i][j] += matrix[i][j-1];
cout << (int)matrix[i][j] << " ";
}
cout << endl;
}
int re = 0;
for(int j=0;j<m;j++)
{
stack<int> st;
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&(matrix[st.top()][j]>=matrix[i][j]))
{
int now = st.top();
st.pop();
int len;
if(st.empty())
len = n;
else
len = st.top();
re = max(re,matrix[now][j]*(len-i-1));
}
st.push(i);
}
while(!st.empty())
{
int now = st.top();
st.pop();
int len;
if(st.empty())
len = n;
else
len = st.top();
re = max(re,matrix[now][j]*len);
}
cout << re << endl;
}
return re;
}
};
