题目描述：
顾名思义，给定n*m大小的01矩阵，要求找到1数量最多的全1子矩阵
问题降阶：
思考二维问题前，先将问题降阶，思考该问题在一维状况下的解决方式会是一个比较好的思路。
题目链接：
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);}elsenow = 0;}return re;}
};一维转二维：
思路：
解决了一维的问题，对于二维问题，完全可以率先按行进行预处理，处理完后矩阵中存储的即使改行到当前位置为止的最长连续1长度。
而为了寻找最大全1矩阵，完全可以遍历每个位置，以预处理的长度作为第一行，分别向上下下找到第一个小于该长度的行，中间的所有行即可用于形成全1矩阵。于是整理复杂度为
代码：
/*
Author Owen_Q
*/#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e3+5;int a[maxn][maxn];int main()
{int n,m;cin >> n >> m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){int tmp;cin >> tmp;if(j==0)a[i][j]=0;elsea[i][j] = a[i][j-1];if(tmp==0)a[i][j] = 0;elsea[i][j]++;}}int re = 0;//cout << re << endl;for(int i=0;i<n;i++){for(int j=0;j<m;j++){//int now = a[i][j];int pos0 = i-1;while(pos0>=0&&a[pos0][j]>=a[i][j])pos0--;int pos1 = i+1;while(pos1<n&&a[pos1][j]>=a[i][j])pos1++;re = max(re,a[i][j]*(pos1-pos0-1));}}cout << re << endl;return 0;
}单调栈优化：
思路：
看到寻找下一个长度更短的行，立刻想到单调栈优化，即可将复杂度降到
至于具体优化策略，则需要整体思路的转化。
相较于原来向上下分别寻找，这次只需要向下维护一个单调栈，每次当元素出栈时，即可利用出栈的行长构造一个全1矩阵。最后将栈清空即可得到最优结果。
代码：
/*
Author Owen_Q
*/#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e3+5;int a[maxn][maxn];int main()
{int n,m;cin >> n >> m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){int tmp;cin >> tmp;if(j==0)a[i][j]=0;elsea[i][j] = a[i][j-1];if(tmp==0)a[i][j] = 0;elsea[i][j]++;}}int re = 0;//cout << re << endl;for(int j=0;j<m;j++){stack<int> st;for(int i=n-1;i>=0;i--){while((!st.empty())&&(a[st.top()][j]>=a[i][j])){int now = st.top();st.pop();re = max(re,a[now][j]*(now-i));}st.push(i);}while(!st.empty()){int now = st.top();st.pop();re = max(re,a[now][j]*(now+1));}}/*for(int i=0;i<n;i++){for(int j=0;j<m;j++){//int now = a[i][j];int pos = i+1;while(pos<n&&a[pos][j]>=a[i][j])pos++;re = max(re,a[i][j]*(pos-i));}}*/cout << re << endl;return 0;
}