【算法学习笔记】浅谈悬线法

悬线法

什么是悬线法？

悬线法是用来解决最大子矩形问题的有力武器，它的思想很简单，代码也很好写。

悬线法的适用范围是单调栈的子集。具体来说，悬线法可以应用于满足以下条件的题目：

  • 需要在扫描序列时维护单调的信息；
  • 可以使用单调栈解决；
  • 不需要在单调栈上二分。

看起来悬线法可以被替代，用处不大，但是悬线法概念比单调栈简单，更适合初学 OI/ACM 的选手理解并解决最大子矩阵等问题。

原理

一般地，我们有一张 \(n∗m\) 的图，里面有一些障碍，我们想要求出一个最大的子矩形，使得它里面没有任何障碍（或者说，使它满足某个条件）。

我们考虑从每个点向上作一条射线，这条线如果遇到一个障碍或者是矩形的上边界就停下。这条线，就叫做悬线。我们把这条线尽可能地往左右移动（尽可能指的是不遇到障碍），就可以围成一个极大子矩形，这个子矩形是这条悬线所能构成的最大的子矩形。

显然，最大子矩形是属于所有悬线能构成的极大子矩形的集合里的。

于是，我们只要枚举每个悬线，\(\mathcal{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]);

当然，意思是这个意思，实现起来会有一些不一样的地方。

最后，我们枚举每个点，统计一下答案就好了。

例题：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;
}

OI wiki 社区

以下引用部分 OI Wiki 的题目讲解，感谢社区的引用许可！

“SP1805 HISTOGRA – Largest Rectangle in a Histogram“

题目大意：在一条水平线上有 \(n\) 个宽为 \(1\) 的矩形，求包含于这些矩形的最大子矩形面积。

悬线，就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。

对于一条悬线，我们在这条上端点不超过当前位置的矩形高度且不移出边界的前提下，将这条悬线左右移动，求出其最多能向左和向右扩展到何处，此时这条悬线扫过的面积就是包含这条悬线的尽可能大的矩形。容易发现，最大子矩形必定是包含一条初始位置为 \(i\)，高度为 \(h_i\) 的悬线。枚举实现这个过程的时间复杂度为 \(O(n ^ 2)\)，但是我们可以用悬线法将其优化到 \(O(n)\)。

我们考虑如何快速找到悬线可以到达的最左边的位置。

定义 \(l_i\) 为当前找到的 \(i\) 位置的悬线能扩展到的最左边的位置，容易得到 \(l_i\) 初始为 \(i\)，我们需要进一步判断还能不能进一步往左扩展。

  • 如果当前 \(l_i = 1\)，则已经扩展到了边界，不可以。
  • 如果当前 \(a_i > a_{l_i – 1}\)，则从当前悬线扩展到的位置不能再往左扩展了。
  • 如果当前 \(a_i \le a_{l_i – 1}\)，则从当前悬线还可以往左扩展，并且 \(l_i – 1\) 位置的悬线能向左扩展到的位置，\(i\) 位置的悬线一定也可以扩展到，于是我们将 \(l_i\) 更新为 \(l_{l_i – 1}\)，并继续执行判断。

通过摊还分析，可以证明每个 \(l_i\) 最多会被其他的 \(l_j\) 遍历到一次，因此时间复杂度为 \(O(n)\)。

【参考代码】

const int N = 100010;
int n, a[N], l[N], r[N];
ll ans;
int main() {
    while (scanf("%d", &n) != EOF && n) {
        ans = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &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, (long long)(r[i] - l[i] + 1) * a[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

“UVA1619 感觉不错 Feel Good“

对于一个长度为 \(n\) 的数列，找出一个子区间，使子区间内的最小值与子区间长度的乘积最大，要求在满足舒适值最大的情况下最小化长度，最小化长度的情况下最小化左端点序号。

本题中我们可以考虑枚举最小值，将每个位置的数 \(a_i\) 当作最小值，并考虑从 \(i\) 向左右扩展，找到满足 \(\min\limits _ {j = l} ^ r a_j = a_i\) 的尽可能向左右扩展的区间 \([l, r]\)。这样本题就被转化成了悬线法模型。

【参考代码】

const int N = 100010;
int n, a[N], l[N], r[N];
long long sum[N];
long long ans;
int ansl, ansr;
bool fir = 1;
int main() {
    while (scanf("%d", &n) != EOF) {
        memset(a, -1, sizeof(a));
        if (!fir)
            printf("\n");
        else
            fir = 0;
        ans = 0;
        ansl = ansr = 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + a[i];
            l[i] = r[i] = i;
        }
        for (int i = 1; i <= n; i++)
            while (a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1];
        for (int i = n; i >= 1; i--)
            while (a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1];
        for (int i = 1; i <= n; i++) {
            long long x = a[i] * (sum[r[i]] - sum[l[i] - 1]);
            if (ans < x || (ans == x && ansr - ansl > r[i] - l[i]))
                ans = x, ansl = l[i], ansr = r[i];
        }
        printf("%lld\n%d %d\n", ans, ansl, ansr);
    }
    return 0;
}

最大子矩形

“P4147 玉蟾宫“

给定一个 \(n \times m\) 的包含 'F' 和 'R' 的矩阵，求其面积最大的子矩阵的面积 \(\times 3\)，使得这个子矩阵中的每一位的值都为 'F'。

我们会发现本题的模型和第一题的模型很像。仔细分析，发现如果我们每次只考虑某一行的所有元素，将位置 \((x, y)\) 的元素尽可能向上扩展的距离作为该位置的悬线长度，那最大子矩阵一定是这些悬线向左右扩展得到的尽可能大的矩形中的一个。

【AC Code】

int m, n, a[1010], l[1010], r[1010], ans;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        char s[3];
        for (int j = 1; j <= m; j++) {
            scanf("%s", s);
            if (s[0] == 'F')
                a[j]++;
            else if (s[0] == 'R')
                a[j] = 0;
        }
        for (int j = 1; j <= m; j++)
            while (a[l[j] - 1] >= a[j]) l[j] = l[l[j] - 1];
        for (int j = m; j >= 1; j--)
            while (a[r[j] + 1] >= a[j]) r[j] = r[r[j] + 1];
        for (int j = 1; j <= m; j++) ans = std::max(ans, (r[j] + l[j] - 1) * a[j]);
    }
    printf("%d", ans * 3);
    return 0;
}

参考

Tags:

VirMach 便宜 VPS

QNews

QNews