题意：给出由01组成的矩阵，求求全是1的次大子矩阵。
思路：
单调栈
全是1的最大子矩阵的变形，不能直接把所有的面积存起来然后排序取第二大的，因为次大子矩阵可能在最大子矩阵里面，比如：
100111111有篇博主的代码细节处理的很好，由于矩阵每行的长度一致，则不必重复在数组末尾标记0；然后由于j是从1，最开始如果push进0的话，有两个好处：
1.可以不受栈之前“残留”的元素m+1的影响
2.不用再判断栈是某为空来确定wid的值
Code
#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 7;int n, m, ans;string str[N];int h[N], mx1, mx2;stack <int> s;void solve(int x){ if(x > mx1) mx2 = mx1, mx1 = x; else if(x > mx2) mx2 = x;}int main(){ scanf("%d%d",&n, &m); for(int i = 1; i <= n; i++) { cin >> str[i]; for(int j = 1; j <= m; j++) { if(str[i][j-1] == '1') h[j] += 1; else h[j] = 0; } s.push(0); for(int j = 1; j <= m + 1; j++) { while(h[j] < h[s.top()]) { int index = s.top(); s.pop(); int x = j - 1 - s.top(), y = h[index]; solve(x * y); solve((x - 1)* y); solve(x * (y - 1)); } s.push(j); } } cout << mx2 << endl;} View Code
悬线法
通过悬线法，可以找到以点（i，j）为底的极大矩形。
u[i][j]、l[i][j]、r[i][j]分别表示以为底的极大矩形的上边界，左边界，右边界；首先预处理：找到点（i，j）可以沿伸的的上端点、左端点，右端点 （dp）
For i = 1 to n For j = 1 to m u[i][j] = (i-1,j)==1 ? u[i-1][j] : i; l[i][j] = (i,j-1)==1 ? l[i][j-1] : j; For j = m to 1 r[i][j] = (i,j+1)==1 ? r[i][j+1] : j;如图找到了（4,3） 的 上端点、左端点，右端点，但是这些边界并没有组成一个矩形，可以（4,3）的上端点为上边界，找到左右边界，这样就可以找到一个以点（4，3）为底、以点（4，3）上界为高的极大矩形。
For i = 1 to n For j = 1 to m if (i-1,j)==1 l[i][j] = max(l[i][j], l[i-1][j] r[i][j] = min(r[i][j], r[i-1][j] 矩形面积就是 (r[i][j] − l[i][j] + 1) ∗ (i − u[i][j] + 1) Code #include<bits/stdc++.h>using namespace std;const int N = 1e3+100;int n, m;int g[N][N];int u[N][N], l[N][N], r[N][N];int hh, ll, rr, bb;char str[N];int main(){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++){ scanf("%s",str+1); for(int j = 1; j <= m; j++ ){ if(str[j] == '1') g[i][j] = 1; else g[i][j] = 0; } } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) u[i][j] = l[i][j] = r[i][j] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(g[i][j] == 0) continue; u[i][j] = g[i-1][j] == 1 ? u[i-1][j] : i; l[i][j] = g[i][j-1] == 1 ? l[i][j-1] : j; } for(int j = m; j >= 1; j--){ if(g[i][j] == 0) continue; r[i][j] = g[i][j+1] == 1 ? r[i][j+1] : j; } } int ans = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(g[i][j] == 0) continue; if(g[i-1][j] == 1) { l[i][j] = max(l[i][j], l[i-1][j]); r[i][j] = min(r[i][j], r[i-1][j]); } if(ans<(r[i][j]-l[i][j]+1)*(i-u[i][j]+1)){ hh = u[i][j] , bb =i; rr = r[i][j],ll=l[i][j]; ans = (r[i][j]-l[i][j]+1)*(i-u[i][j]+1); } } } int ans2 = max((rr-ll)*(bb-hh+1), (rr-ll +1)*(bb-hh)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(g[i][j] == 0) continue; if(hh==u[i][j]&&bb==i&&ll==l[i][j]&&rr==r[i][j]) continue; if(ans2<(r[i][j]-l[i][j]+1)*(i-u[i][j]+1)){ ans2=(r[i][j]-l[i][j]+1)*(i-u[i][j]+1); } } } cout << ans2 << endl; return 0;} View Code悬线法的学习可以参考这篇博客（小声bb：虽然感觉现在没什么用，还不如单调栈）
https://blog.csdn.net/dbc_121/article/details/77503611
转载于:https://www.cnblogs.com/wizarderror/p/11335800.html