Rday7

Rday7

单调栈

单调栈

定义:

单调栈,顾名思义,是栈内元素保持一定单调性(单调递增或单调递减)的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。既然是栈,就满足后进先出的特点。与之相对应的是单调队列。

实现:

例如实现一个单调递增的栈,比如现在有一组数10,3,7,4,12。从左到右依次入栈,则如果栈为空或入栈元素值小于栈顶元素值,则入栈;否则,如果入栈则会破坏栈的单调性,则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

10入栈时,栈为空,直接入栈,栈内元素为10。
3入栈时,栈顶元素10比3大,则入栈,栈内元素为10,3。
7入栈时,栈顶元素3比7小,则栈顶元素出栈,此时栈顶元素为10,比7大,则7入栈,栈内元素为10,7。
4入栈时,栈顶元素7比4大,则入栈,栈内元素为10,7,4。
12入栈时,栈顶元素4比12小,4出栈,此时栈顶元素为7,仍比12小,栈顶元素7继续出栈,此时栈顶元素为10,仍比12小,10出栈,此时栈为空,12入栈,栈内元素为12。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* 本伪代码对应的是单调递减栈
*共n个元素,编号为0~n-1
*/
while(栈为空) 栈顶元素出栈; //先清空栈
a[n]=-1;
for(i=0;i<=n;i++)
{
if(栈为空或入栈元素大于等于栈顶元素) 入栈;
else
{
while(栈非空并且栈顶元素大于等于入栈元素)
{
栈顶元素出栈;
更新结果;
}
将最后一次出栈的栈顶元素(即当前元素可以拓展到的位置)入栈;
更新最后一次出栈的栈顶元素其对应的值;
}
}
输出结果;

应用:

以上就是一个单调栈的定义及其实现,下面就来说一下它可以解决哪些问题。碰到问题时就需要灵活运用了。

1.最基础的应用就是给定一组数,针对每个数,寻找它和它右边第一个比它大的数之间有多少个数。
2.给定一序列,寻找某一子序列,使得子序列中的最小值乘以子序列的长度最大。
3.给定一序列,寻找某一子序列,使得子序列中的最小值乘以子序列所有元素和最大。

Bad Hair Day

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.

Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

=

= =
= - = Cows facing right –>
= = =
= - = = =
= = = = = =
1 2 3 4 5 6
Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow’s hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow’s hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input
Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.
Output
Line 1: A single integer that is the sum of c 1 through cN.

1
2
3
4
5
6
7
8
9
10
Sample Input
6
10
3
7
4
12
2
Sample Output
5

题意:
也就是说针对每只牛,啊,不,每头牛求它到它右边第一个比它高(或身高相等)的牛之间有多少头牛,然后将求得的结果相加就是最后的答案。朴素的做法是针对每头牛去寻找右边比它高的牛的位置,时间复杂度为O(n^2),如果用单调栈的话就是O(n).
利用根据单调递增栈解决,如果栈为空或入栈元素小于栈顶元素则入栈,否则会破坏栈的单调性,则将栈顶元素出栈并更新结果,直到栈为空或碰到一个小于入栈元素的值。然后将当前元素入栈。

设数组的最后一个元素为最大值,也就相当于在最右边的牛的右边设了一个高度无限高的牛。这样做的目的是,最后让栈内的元素全部出栈。

PS:代码中的单调栈保存的是牛的位置。结果应该用long long 型,最多有80000头牛,每头牛右边最多有80000头牛,8000080000=6.410^9,而int最多表示大约为2*10^9……

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<stdio.h>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;
int a[maxx], n, top;
int main()
{
int n;
while(~scanf("%d",&n))
{
stack<int> s;
ll ans = 0;
while(!s.empty()) s.pop();
for(int i = 0; i < n; i ++) cin >> a[i];
a[n] = INF;
for(int i = 0; i <= n; i ++)
{
//如果栈为空或入栈元素小于栈顶元素,则入栈
if(s.empty() || a[i] < a[s.top()])
s.push(i);
else
{
//如果栈不为空并且栈顶元素不大于入栈元素,则将栈顶元素出栈
while(!s.empty() && a[i] >= a[s.top()])
{
//获取栈顶元素
top = s.top();
//栈顶元素出栈
s.pop();
//两坐标之差减去一
ans += (i - top - 1);
// cout << i << " " << top << " " << ans << '\n';
}
//当前元素入栈,为了不影响坐标位置
s.push(i);

}
}
cout << ans << '\n';
}

return 0;
}

Largest Rectangle in a Histogram

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,…,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

1
2
3
4
5
6
7
8
9
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000
Hint
Huge input, scanf is recommended.

题意:
对于每个矩形,我们求出它向左向右分别能延伸的长度,然后乘以它的高度,这就是以当前矩形为最低高度可以得到的最大的面积。只需要求个最大值即可。总结性的来说就是:给定一序列,寻找某一子序列,使得子序列中的最小值乘以子序列的长度最大。这是单调栈的一种应用。
构造一个单调递减的单调栈,如果栈为空或入栈元素大于等于栈顶元素则入栈,否则会破坏栈的单调性,将大于入栈元素的栈顶元素出栈,直到栈为空或遇到一个小于等于入栈元素的元素。然后将最后一次出栈的栈顶元素向左向右延伸,也就是确定以栈顶元素的高度为最低高度的矩形的宽度,改变其对应的值,然后入栈。
并且将数组最后一个元素设为最小值,以最后清空栈内所有元素。

注意:
1.单调栈保存的是每个矩形的编号,也就是位置。
2.在维护单调栈,也就是每个矩形向左向右延伸的过程中会使原来数组的值改变。
3.数据很大,要用long long型。
4.最后一次出栈的栈顶元素就是当前入栈元素可以向左拓展到的最大距离。

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5 + 7;

int flag;
ll a[maxx], n;
int main()
{
ll ans, tem = 0;
stack<int> s;
while(~scanf("%lld",&n))
{
if(n == 0) break;
while(!s.empty()) s.pop();
memset(a, 0, sizeof a);
ans = 0;
for(int i = 0; i < n; i ++)
scanf("%lld",&a[i]);
a[n] = -1;//清空栈
for(int i = 0; i <= n; i ++)
{
//如果栈为空或者入栈元素大于等于栈顶元素,入栈
if(s.empty() || a[i] >= a[s.top()])
s.push(i);
else
{
//如果栈不为空并且入栈元素比栈顶元素小的时候才能更新面积
while(!s.empty() && a[i] < a[s.top()])
{
//标记栈顶元素
flag = s.top();
s.pop();
//出栈过程中计算面积
tem = (i - flag) * a[flag];
ans = max(ans, tem);
}
//只将可以延伸到的最左端的位置入栈
s.push(flag);
//并修改该位置的值
a[flag] = a[i];
}
}
printf("%lld\n",ans);
}
return 0;
}

Feel Good

Description
Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people’s memories about some period of life.
A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.
Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.
Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.
Input
The first line of the input contains n - the number of days of Bill’s life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, … an ranging from 0 to 106 - the emotional values of the days. Numbers are separated by spaces and/or line breaks.
Output
Print the greatest value of some period of Bill’s life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill’s life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them.

1
2
3
4
5
6
Sample Input
6
3 1 6 4 5 2
Sample Output
60
3 5

题意:
求序列中的最小值乘以这个序列的和的值最大,是典型的单调栈的应用。一般的思路是求每个数字所在的能使其值为区间最小值的最大区间,然后求出区间元素和乘以该值并更新结果的最大值。普通的做法时间复杂度为O(n^2),用单调栈可以达到O(n)。
用一个单调递减栈,如果栈为空或入栈元素大于等于栈顶元素,则入栈,否则将破坏栈的单调性,则将栈顶元素出栈,直到栈为空或碰到第一个小于等于入栈元素的元素。然后将最后一次出栈的栈顶元素入栈,并将其向左右拓展,并更新其对应的值。
由于维护单调栈会改变原数组的值,同时为了方便求区间元素值,我们设置一个sum数组,记录前缀和。
我们将原数组的最后一个值设为最小值,以方便最后将栈内所有元素出栈。

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long LL;

int main()
{
//pos1和pos2记录区间的开始和结束位置
int i,n,pos1,pos2;
//tmp为临时变量,记录区间内的和;top指向栈顶元素;ans为结果;sum为前缀和
LL tmp,top,ans,a[100010],sum[100010];
stack<int> st; //单调栈,记录元素位置
while(~scanf("%d",&n))
{
while(!st.empty()) st.pop(); //清空栈
sum[0]=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i]; //计算前缀和
}
a[n+1]=-1; //将最后一个设为最小值,以最后让栈内元素全部出栈
ans=0;
for(i=1;i<=n+1;i++)
{
if(st.empty()||a[i]>=a[st.top()])
{ //如果栈为空或入栈元素大于等于栈顶元素,则入栈
st.push(i);
}
else
{
while(!st.empty()&&a[i]<a[st.top()])
{ //如果栈非空并且入栈元素小于栈顶元素,则将栈顶元素出栈
top=st.top();
st.pop();
tmp=sum[i-1]-sum[top-1]; //计算区间内元素和
tmp*=a[top]; //计算结果
if(tmp>=ans)
{ //更新最大值并记录位置
ans=tmp;
pos1=top;
pos2=i;
}
}
st.push(top); //将最后一次出栈的栈顶元素入栈
a[top]=a[i]; //将其向左向右延伸并更新对应的值
}
}
printf("%lld\n",ans);
printf("%d %d\n",pos1,pos2-1);
}
return 0;
}

---------------- The End ----------------
0%