【算法与数据结构】——悬线法

男娘i 2022-08-31 05:56 113阅读 0赞

# 悬线法 #

悬线法主要用来解决最大子矩形问题，它的思想比较简单，代码也很好写。

悬线法的适用范围是最大子矩阵。具体来说，悬线法可以应用于满足以下条件的题目：

*  需要在扫描序列时维护单调的信息，比如某种最大值；
 *  可以使用单调栈解决；
 *  不需要在单调栈上二分。

看起来悬线法可以被替代，用处不大，但是悬线法概念比单调栈简单一些。

# 原理 #

一般地，我们有一张 n∗m 的图，里面有一些障碍，我们想要求出一个最大的子矩形，使得它里面没有任何障碍（或者说，使它满足某个条件）。  
我们考虑从每个点向上作一条射线，这条线如果遇到一个障碍或者是矩形的上边界就停下。这条线，就叫做悬线。我们把这条线尽可能地往左右移动（尽可能指的是不遇到障碍），就可以围成一个极大子矩形，这个子矩形是这条悬线所能构成的最大的子矩形。  
显然，最大子矩形是属于所有悬线能构成的极大子矩形的集合里的。  
于是，我们只要枚举每个悬线，O(n) 地算出每个极大子矩形的面积，然后取一个 max 就行了。  
考虑每一个点和每一条悬线一一对应，且一共有 n∗m 个点，所以复杂度就是 O(nm)。  
那么，问题就转化为如何 O(1) 地算出每个极大子矩形的面积。  
举个例子，我们假设我们要求矩形里都是相同的数。  
我们考虑递推，设H\[i\]\[j\] 表示 以(i,j)为起点的悬线长度。  
则存在

if (a[i][j] == a[i - 1][j]) H[i][j] = H[i - 1][j] + 1;
    else H[i][j] = 1;

然后我们再考虑左右边界，记为 L\[i\]\[j\],R\[i\]\[j\] ，这也是可以递推的。

//Lx, Rx表示在这一行中以(i,j)为起点的悬线能达到最左边和最右边的位置
    if (a[i][j] == a[i - 1][j])
        L[i][j] = max(L[i - 1][j], Lx[i][j]), R[i][j] = min(R[i - 1][j], Rx[i][j]);

# 例题 #

[1008][]求一个每一列都是非递减的最大子矩阵

[ZJOI2007 棋盘制作][ZJOI2007]  
AC Code

const int N = 2e3 + 10;
    int a[N][N];
    int H[N][N], L[N][N], R[N][N];
    
    int main() { 
        cin.tie(nullptr)->sync_with_stdio(false);
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> a[i][j], L[i][j] = R[i][j] = j, H[i][j] = 1;
    
        for (int i = 1; i <= n; ++i) { 
            for (int j = 2; j <= m; ++j)
                L[i][j] = a[i][j] == a[i][j - 1] ? j : L[i][j - 1];
            for (int j = m - 1; j >= 1; --j)
                R[i][j] = a[i][j] == a[i][j + 1] ? j : R[i][j + 1];
        }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) { 
                if (i > 1 and a[i][j] != a[i - 1][j]) { 
                    H[i][j] = H[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]);
                }
            }
    
        int ans1 = 0, ans2 = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) { 
                int a = H[i][j], b = R[i][j] - L[i][j] + 1;
                if (a > b) swap(a, b);
                ans1 = max(ans1, a * a);
                ans2 = max(ans2, a * b);
            }
    
        cout << ans1 << "\n" << ans2;
    }

[1008]: https://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&cid=984
[ZJOI2007]: https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-1057