POJ2796-Feel Good
- 最大矩形
题目链接
题目大意：给出一个数列，在数列中找出这样一个区间，使得区间的和乘以区间的最小值最大。
这道题是在做单调栈专题的时候写到的，先通过一道经典题介绍一下单调栈是什么
这道题的意思是：给出n个矩形，每个矩形的宽度都为1，高度是输入的值。设区间的面积为区间内所有矩形的宽度之和乘以区间内最矮矩形的高度，问面积最大的区间面积是多大。
暴力的解法是枚举所有的区间找出最大面积，但这么写肯定超时。
稍加思考：如果能保证后面的矩形都不比前面的矩形低，那么只要从前往后，算出每个矩形的高度与它后面所有矩形的总宽度的乘积，最后取个最大值，就是最终的答案了。但题目没有保证后面的矩形不比前面的矩形低，如果突然出现一个比前面的矩形矮的矩形（类似一个波谷），这个做法就不行了。
但当这种情况出现时，实际上可以经过处理，继续维持原序列的单调性。若波谷在第i个矩形处出现，那么原序列长度为i的这个前缀如果要与后面相连的话，所能取得的最高高度不可能大于i的高度；另一方面，对于原序列长度为i的前缀的后缀，在与前面相连相连时，所能取得的最高高度也不可能大于区间内最矮的元素，由于这个前缀是不下降的，也就是不可能矮于区间内最矮的元素。基于这两点，当处理到一个波谷时，可以将它前面所有比它高的矩形先一直往前，求个最大值，更新一下答案。之后，由于比它高的矩形的高度在后续计算中不会再用到，后续就可以将这些比它高的矩形统一视为跟它一样高，这样就保证了序列的不下降性。
整个过程其实基于一个栈型结构操作：每次比较待入栈的元素与栈顶元素的大小（在这道题中，大小指对应矩形的高度），如果待入栈元素不小于栈顶元素，就直接入栈；否则先将栈中比待入栈元素大的元素求个最大值，然后将这些原本大于待入栈元素的元素的值都改成待入栈元素的高度，重新入栈，最后将待入栈元素入栈。保证了栈从栈底到栈顶一直是不下降的。
这种保持栈顶到栈底所有元素拥有一定单调性的栈就是单调栈。入栈/维护的大致代码框架如下
1
2
3
4
5
6
7
8
9
10
| for(待入栈元素a)
{
if(a与栈顶元素满足栈的单调性)
直接入栈;
else
{
处理掉栈顶所有不满足与a单调性的元素;
将a入栈;
}
}
|
其中，“处理掉栈顶所有不满足与a单调性的元素”的方法这一步没有固定的方法，需要因题目而异。比如在这一道比较模板的题中，需要注意到已入栈，且高于待入栈矩形的那些矩形在后续处理中都可以将高度视为待入栈矩形的高度，依此来保证栈的单调性。
需要注意的一点是，构造完整个序列的单调栈不一定意味着题目的结束。之所以构造单调栈，只是因为元素的单调性能够使求解更为简单，在完成了单调栈后，还应通过保证单调性后得以实现的简单方法将整个序列再求一次答案。下面就是这一道经典题的完整代码
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
struct rect
{
long long wid, hei;
rect(long long w = 1, long long h = 0)
{
wid = w;
hei = h;
}
};
int main()
{
int n;
while (scanf("%d", &n))
{
if (n == 0)
return 0;
stack<rect> s;
long long res = 0;
for (int i = 1; i <= n; i++)
{
rect a;
scanf("%lld", &a.hei);
if (s.empty() || a.hei >= s.top().hei)
{
s.push(a);
continue;
}
rect p(0, 0);
while (!s.empty())
{
if (s.top().hei < a.hei)
break;
p.wid += s.top().wid;
p.hei = s.top().hei;
s.pop();
if (res < p.wid * p.hei)
res = p.wid * p.hei;
}
p.wid += a.wid;
p.hei = a.hei;
s.push(p);
}
rect p(0, 0);
while (!s.empty())
{
p.wid += s.top().wid;
p.hei = s.top().hei;
s.pop();
if (res < p.wid * p.hei)
res = p.wid * p.hei;
}
printf("%lld\n", res);
}
return 0;
}
|
小结：如果一道题中的元素在一定规则下单调时能使题目易于求解，且存在让原序列经过不改变最终答案的处理后变得单调的方法，那么这一题用单调栈来做。
以本文所说的题目（POJ2796）为例：如果序列中点的权值都是单调不下降的，那么只需要对于每个点，求出它的权值乘以它后面所有点的权值和，用这个积更新答案即可。当序列的中间出现了波谷，用波谷前面权值不低于谷底的点求出一个答案，再将它们赋为谷底的权值，并不影响后续的计算，同时也维持了序列的单调性，因此就可以使用单调栈来解决此题
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
struct node
{
long long sum, num;
int r, l;
};
int main()
{
int n, i;
while (~scanf("%d", &n))
{
stack<node> s;
long long res = -1;
int rr, rl;
for (i = 1; i <= n; i++)
{
node a;
scanf("%lld", &a.sum);
a.num = a.sum;
a.l = a.r = i;
if (s.empty() || a.num >= s.top().num)
{
s.push(a);
continue;
}
node p;
p.sum = 0;
p.r = i - 1;
while (!s.empty())
{
if (a.num > s.top().num)
break;
p.sum += s.top().sum;
p.num = s.top().num;
p.l = s.top().l;
s.pop();
if (res < p.sum * p.num)
{
res = p.sum * p.num;
rl = p.l;
rr = p.r;
}
}
p.sum += a.sum;
p.num = a.num;
p.r = a.r;
s.push(p);
if (res < p.sum * p.num)
{
res = p.sum * p.num;
rl = p.l;
rr = p.r;
}
}
node p;
p.num = p.sum = 0;
p.l = p.r = n;
while (!s.empty())
{
p.sum += s.top().sum;
p.num = s.top().num;
p.l = s.top().l;
s.pop();
if (res < p.sum * p.num)
{
res = p.sum * p.num;
rl = p.l;
rr = p.r;
}
}
printf("%lld\n%d %d\n", res, rl, rr);
}
return 0;
}
|