懸線法
引入
懸線法的適用範圍是單調棧的子集。具體來説，懸線法可以應用於滿足以下條件的題目：
- 需要在掃描序列時維護單調的信息；
- 可以使用單調棧解決；
- 不需要在單調棧上二分。
看起來懸線法可以被替代，用處不大，但是懸線法概念比單調棧簡單，更適合初學 OI 的選手理解並解決最大子矩陣等問題。
例題
SPOJ 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)\)。
實現
參考代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | #include <algorithm>
#include <cstdio>
using std::max;
const int N = 100010;
int n, a[N];
int l[N], r[N];
long long 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]\)。這樣本題就被轉化成了懸線法模型。
參考代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | #include <cstdio>
#include <cstring>
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)\) 的元素儘可能向上擴展的距離作為該位置的懸線長度，那最大子矩陣一定是這些懸線向左右擴展得到的儘可能大的矩形中的一個。
參考代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | #include <algorithm>
#include <cstdio>
int m, n, a[1010], l[1010], r[1010], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
l[j] = r[j] = j;
}
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 (l[j] != 1 && a[l[j] - 1] >= a[j]) l[j] = l[l[j] - 1];
for (int j = m; j >= 1; j--)
while (r[j] != m && 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;
}
|
習題
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：mwsht, sshwy, ouuan, Ir1d, Henry-ZHR, hsfzLZH1
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用