• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

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

55分钟前 1次浏览

## 悬线法

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

## 原理

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

``````//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]);
``````

【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 社区

### “SP1805 HISTOGRA – Largest Rectangle in a Histogram”

• 如果当前 (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})，并继续执行判断。

【参考代码】

``````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("%lldn", ans);
}
return 0;
}
``````

### “UVA1619 感觉不错 Feel Good”

【参考代码】

``````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("%lldn%d %dn", ans, ansl, ansr);
}
return 0;
}
``````

### 最大子矩形

“P4147 玉蟾宫”

【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;
}
``````

## 参考

• 知乎：悬线法求解最大矩型（DP）
• PPT：浅谈用极大化思想解决最大子矩形问题
• 洛谷：悬线法浅谈