感悟:
单调栈关键是要保证栈内是一个单调的关系,所以就是要想栈底到栈顶递减,就是data[i]<=top就一直弹,直到找到比我打的形成递减才行
然后就是一个无脑弹出
之后空的情况一种
不空的情况直接取出栈顶
最后无脑压入
题目描述
约翰有 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≤105,
1≤Hi≤106
输入样例:
6
3
2
6
1
1
2
输出样例:
3
3
0
6
6
0
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
C++ 代码
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
#define N 100010
int n;
int H[N];
int ans[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&H[i]);
stack<int> st;
for(int i=n;i>=1;i--)
{
while(!st.empty() && H[st.top()]<=H[i])
{
st.pop();
}
if(st.empty())
{
ans[i]=0;
}
else
{
ans[i]=st.top();
}
st.push(i);
}
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}