悬线法—最大子矩形|天天百事通

我们在做题的时候经常会遇到一些求最大子矩形的问题，而这个时候就有人用单调栈来解决，实际上我们可以用一种名为悬线法的更易于理解的方法来求解。

悬线法，我也不知道为啥叫这个名字。

我们对于一个 \(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\) 过百万会寄，一般都是用第二种用一维数组的。

很板的题目，直接来看代码：

其实我们可以在输入的时候直接做，但是我觉得看上去不美观。

我们在扩展的时候其实是有时候需要判断当前点能否扩展，后面有的题目会涉及到。

#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。