我们在做题的时候经常会遇到一些求最大子矩形的问题，而这个时候就有人用单调栈来解决，实际上我们可以用一种名为悬线法的更易于理解的方法来求解。
思想悬线法，我也不知道为啥叫这个名字。
我们对于一个 \(n\times m\) 的矩阵，我们如果想要找到他最大的子矩形，我们首先需要知道哪里能扩展，哪里不能扩展，而我们在求解的时候，一行一行的进行求解。
【资料图】
我们维护三个数组 \(l,r,up\) 分别表示当前点能向左扩展到哪个点，当前点能向右扩展到哪个点，以及向上能够扩展到哪个点。
我们在处理当前点的时候，无非就三种情况：
当前点到了边界，也就是 \(l[j] = 1,r[j] = m\) 的情况，此时不能继续扩展。
如果当前点的 \(up[j] > up[l[j] - 1]\) 那么是不可以继续扩展的。
如果当前点的 \(up[j]\le up[l[j]-1]\) 那么我们可以继续扩展，我们扩展的时候可以发现，如果当前点可以扩展到 \(l[j] - 1\) 的话，我们是可以扩展到 \(l[l[j]-1]\) 的，所以我们可以直接替换掉的。
一般的代码有两种写法，一种是都开二维数组的，我不推荐使用这种，因为只要空间一紧或者想试试 \(n^2\) 过百万会寄，一般都是用第二种用一维数组的。
例题：[POI2002] 最大的园地 - 洛谷很板的题目，直接来看代码：
其实我们可以在输入的时候直接做，但是我觉得看上去不美观。
我们在扩展的时候其实是有时候需要判断当前点能否扩展，后面有的题目会涉及到。
#include #define int long long#define N 2010using namespace std;int n, m, a[N][N], l[N], r[N], up[N], ans;signed main(){ cin >> n, m = n; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) cin >> a[i][j]; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) l[j] = r[j] = j; for(int j = 1; j <= m; j ++) { if(a[i][j] == 0) up[j] ++; else up[j] = 0; } for(int j = 1; j <= m; j ++) while(l[j] > 1 && up[l[j] - 1] >= up[j]) l[j] = l[l[j] - 1]; for(int j = m; j >= 1; j --) while(r[j] < m && up[r[j] + 1] >= up[j]) r[j] = r[r[j] + 1]; for(int j = 1; j <= m; j ++) ans = max((r[j] - l[j] + 1) * up[j], ans); } cout << ans << endl; return 0;} 和上面题目的区别就是 \(01\) 换成了 \(\text{EF}\)，最后结果要乘三。
#include #define INF 0x3f3f3f3f#define int long long#define N 1010using namespace std;int n, m, ans, a[N][N], up[N][N], lf[N][N], rf[N][N];signed main(){ cin >> n >> m; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { char s; cin >> s; a[i][j] = (s == "F"); } } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(a[i][j]) { up[i][j] = up[i - 1][j] + 1; lf[i][j] = lf[i][j - 1] + 1; } if(a[i][m - j + 1]) rf[i][m - j + 1] = rf[i][m - j + 2] + 1; } } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(a[i][j] && a[i - 1][j]) { lf[i][j] = min(lf[i][j], lf[i - 1][j]); rf[i][j] = min(rf[i][j], rf[i - 1][j]); } ans = max(ans, (rf[i][j] + lf[i][j] - 1) * up[i][j]); } } cout << ans * 3 << endl; return 0;} 这个题目看起来需要用单调栈，但实际上悬线法也可以，这个的区别就是我们还是和前面一样，只不过把每组数据看作是一行，\(up\) 是一开始给我们的来处理就好了。
#include #define int long long#define N 1000100using namespace std;int n, a[N], l[N], r[N], ans;signed main(){ while(1) { cin >> n; if(n == 0) break; ans = 0; for(int i = 1; i <= n; i ++) cin >> a[i], l[i] = r[i] = i; for(int i = 1; i <= n; i ++) while(l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1]; for(int i = n; i >= 1; i --) while(r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1]; for(int i = 1; i <= n; i ++) ans = max(ans, (r[i] - l[i] + 1) * a[i]); cout << ans << endl; } return 0;} 这个题目和上面的思路一样，也是可以看作是求最大子矩形的面积。
#include #define int long long#define N 100100using namespace std;int n, a[N], l[N], r[N], sum[N], ans, ansl, ansr, flag = 1;signed main(){ while(cin >> n) { if(n == EOF) break; memset(a, -1, sizeof a); if(flag == 0) cout << endl; else flag = 0; ans = 0; ansl = ansr = 1; for(int i = 1; i <= n; i ++) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; l[i] = r[i] = i; } for(int i = 1; i <= n; i ++) while(a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1]; for(int i = n; i >= 1; i --) while(a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1]; for(int i = 1; i <= n; i ++) if((sum[r[i]] - sum[l[i] - 1]) * a[i] > ans) ans = (sum[r[i]] - sum[l[i] - 1]) * a[i], ansl = l[i], ansr = r[i]; cout << ans << endl; cout << ansl << " " << ansr << endl; } return 0;} 区别是我们的边界上可以有障碍。
我们看数据范围就知道我们直接枚举点会炸，而我们知道如果要是找最大子矩形的话，肯定是边界上带障碍更优，所以我们可以直接枚举所有障碍的点来一个一个计算，我们首先要把四个边界点给加进去，然后分两种情况讨论：
当前障碍 \(i\) 横坐标比 \(j\) 大，那么我们就要更新左边界。
当前障碍 \(i\) 横坐标比 \(j\) 小，那么我们就要更新右边界。
code:
#include #define int long long#define N 100010using namespace std;struct sb{int x, y;}e[N];int L, W, n, x, y, ans;inline int cmp1(sb x, sb y){return x.x < y.x || x.x == y.x && x.y < y.y;}inline int cmp2(sb x, sb y){return x.y < y.y || x.y == y.y && x.x < y.x;}inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!="-";ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}signed main(){L = read(); W = read(); n = read(); for(int i = 1; i <= n; i ++) { x = read(), y = read(); e[i] = (sb){x, y};//障碍物 } e[++ n] = (sb){0, 0};//边界障碍物 e[++ n] = (sb){0, W};e[++ n] = (sb){L, 0};e[++ n] = (sb){L, W}; sort(e + 1, e + n + 1, cmp1);//按x从小到大排序 for(int i = 1; i <= n; i ++)//遍历所有障碍 { int le = 0, ri = W, cnt = i; while(e[i].x == e[cnt].x) cnt ++;//是同一行就一直加 int j = cnt;//取出cnt while(j <= n)//只要不超过最大个数 { ans = max(ans, (e[j].x - e[i].x) * (ri - le));//计算当前两个障碍的的面积 if(e[j].y <= e[i].y) le = max(le, e[j].y);//如果要是当前的第二个点的列比第一个的小，就更新le else ri = min(ri, e[j].y);//否则就更新x j ++;//往后找 } }sort(e + 1, e + n + 1, cmp2);//竖着找、 for(int i = 1; i <= n; i ++){ int le = 0, ri = L, cnt = i; while(e[i].y == e[cnt].y) cnt ++; int j = cnt; while(j <= n){ ans = max(ans, (e[j].y - e[i].y) * (ri - le)); if(e[j].x <= e[i].x) le = max(le, e[j].x); else ri = min(ri, e[j].x); j ++; } }cout << ans << endl; return 0;} 这个题目其实也不难。
我们在处理 \(up\) 的时候，我们可以发现能扩展的条件是和上面的不一样，所以我们可以用异或来达到这个操作。
我们在扩展左右边界的时候也是同理，我们不能只判断 \(up\) 和边界了，我们需要同时看一下能不能向两边扩展才行。
code:
#include #define int long long#define N 2100using namespace std;int n, m, a[N][N], l[N], r[N], up[N], ans1, ans2;signed main(){cin >> n >> m;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin >> a[i][j];for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++)l[j] = r[j] = j;for(int j = 1; j <= m; j ++){if(a[i][j] ^ a[i - 1][j]) up[j] ++;else up[j] = 1;}for(int j = 1; j <= m; j ++)while(l[j] != 1 && a[i][l[j]] ^ a[i][l[j] - 1] && up[l[j] - 1] >= up[j]) l[j] = l[l[j] - 1];for(int j = m; j >= 1; j --)while(r[j] != m && a[i][r[j]] ^ a[i][r[j] + 1] && up[r[j] + 1] >= up[j])r[j] = r[r[j] + 1];//cout << "cao" << endl;for(int j = 1; j <= m; j ++){int xx = min(r[j] - l[j] + 1, up[j]);ans1 = max(ans1, xx * xx);ans2 = max(ans2, (r[j] - l[j] + 1) * up[j]);}}cout << ans1 << endl << ans2 << endl;return 0;} 参考自 OI Wiki。
关键词：
56位残疾人士登上黄山 互利互勉共建生活希望 中国新闻网
悬线法—最大子矩形_世界速讯 博客园
中国石油北京项目管理公司：胡继勇已不再履行法定代表人职责 北京日报客户端
江东时评 | 当好过滤焦虑的“筛子” 百度新闻
环球热点！四大家族私人档案 个人图书馆-若悟369