仰视奶牛(单调栈模板题)

83 阅读 0 评论 55 点赞

我是靠谱客的博主机灵口红，这篇文章主要介绍仰视奶牛(单调栈模板题)，现在分享给大家，希望可以做个参考。

题目描述

题目链接
约翰有N头奶牛，编号为1到N。

现在这N头奶牛按编号从小到大的顺序站成了一排，其中奶牛 i 的身高为Hi。

现在，每头奶牛都向它的右侧望向那些编号较大的奶牛，对于奶牛 i 如果存在一头奶牛 j 满足 i<j 并且 Hi<Hj，那么我们称奶牛 i 需要仰视奶牛 j。

请你求出每头奶牛的最近仰视对象。

输入格式
第一行包含整数N。

接下来N行，每行包含一个整数Hi，其中第 i 行的数为编号为 i 的奶牛的高度。

输出格式
共 N 行，每行输出一个整数，其中第 i 行的输出整数表示编号为 i 的奶牛的最近仰视对象的编号，如果不存在仰视对象，则输出0。

数据范围
1≤N≤10⁵
1≤Hi≤10⁶

输入样例：

复制代码

输出样例：

复制代码

解题思路：

本题是单调栈的基本题目，接下来分别通过单调递增栈和单调递减栈来完成

首先是单调递减栈，即栈中的元素为单调递减,这里我们是在出栈的时候对栈顶元素要仰望的值进行赋值。我们可以这样考虑：当出现比栈顶元素大的数时，即栈顶元素要仰望的就是该数，然后不断将栈顶元素出栈，直到栈为空或者栈顶元素大于等于当前元素。否则就将该数压栈。到最后栈中剩下的元素都是没有仰望对象的牛，因为L数组为全局变量初始就为0，所以我们不去处理它。

复制代码

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
#include<cstdio>
#include<iostream>  
#include<stack>
using namespace std;
int a[100010];
int L[100010];
int main(void){
	stack<int> st;
	int N;
	cin >> N;
	for(int i = 1 ; i <= N;i++){
		cin >> a[i];
	}
	for(int i = 1; i <= N;i++){
		while(st.size() && a[st.top()] < a[i]){
			L[st.top()] = i;
			st.pop();
		}
		st.push(i);
	}
	for(int i = 1 ; i <= N;i++){
		cout << L[i] << endl;;
	}
	return 0;
}

接下来是单调递增栈的思路，也是我一开始学习单调栈的写法，因为我们是要仰望右边的数所有我们从最右边开始处理，如果当前元素大于等于栈顶元素那就不断将栈中元素弹出，直到栈顶元素比当前元素大或者栈为空。之后若栈为空则没有要仰视的牛，否则要仰视的即为栈顶元素。

复制代码

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
#include<cstdio>
#include<iostream>  
#include<stack>
using namespace std;
int a[100010];
int L[100010];
int main(void){
	stack<int> st;
	int N;
	cin >> N;
	for(int i = 1 ; i <= N;i++){
		cin >> a[i];
	}
	for(int i = N; i > 0;i--){
		while(st.size() && a[st.top()] <= a[i])
			st.pop();
		if(st.empty()) 
			L[i] = 0;
		else
			L[i] = st.top();
		st.push(i);
	}
	for(int i = 1 ; i <= N;i++){
		cout << L[i] << endl;;
	}
	return 0;
}