题型整理（4）

单调栈

1.视野总和

描述：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。

输入：4 3 7 1
输出：2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int FieldSum(vector<int>& v){
	v.push_back(INT_MAX);//压入最大值保证栈中元素能完全出栈
	stack<int> st;
	int sum = 0;
	for (int i = 0; i < (int)v.size(); i++){
		if (st.empty() || v[st.top()] > v[i])
			st.push(i);
		else{
			while (!st.empty() && v[st.top()] <= v[i]){
				int top = st.top();
				st.pop();
				sum += (i - top - 1);
			}
			st.push(i);
		}
	}
	return sum;
}

2.柱状图中的最大矩形

描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 , 求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入：2 1 5 6 2 3

输出：10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxS(vector<int>& heights) {
     heights.push_back(0);//压入最小值保证栈中元素能完全出栈
     stack<int> stk;
     int maxs= 0;
     for(int i = 0;i<heights.size();i++){
         while(!stk.empty() && heights[i]<heights[stk.top()]){
             int top= stk.top();
             stk.pop();
             maxs = max(maxs,heights[top]*(stk.empty()? i:(i - stk.top() -1)));
		 }
         stk.push(i);
     }
     return maxs;
}

3.求最大区间

描述：给出一组数字，求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点

输入：3 1 6 4 5 2

输出：60
       3 5

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
#include<stdio.h>
#include<iostream>
#include<stack>
using namespace std;
typedef long long LL;
int main()
{
	int i,n,pos1,pos2; //pos1和pos2记录区间的开始和结束位置 
	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;
}