Acwing 600. 仰视奶牛(stack记录成对数写法)(每头奶牛的最近仰视对象)

地址:https://www.acwing.com/problem/content/602/

Acwing 600. 仰视奶牛(stack记录成对数写法)(每头奶牛的最近仰视对象)

Acwing 600. 仰视奶牛(stack记录成对数写法)(每头奶牛的最近仰视对象)

既然是离自己最近,可以想到栈

对于当前数,把它左边数的视为栈。

每次ai与栈顶比较,

如果发现栈顶<ai,说明它可以被栈顶仰视,记录下标。同时清掉栈顶。为什么要清掉呢?因为题目要求的是找最近,既然栈顶已经找到最近答案,后续就用不到它了,所以清掉即可。

否则,while结束。为什么结束?因为栈顶大于>=ai的话,栈里其他的元素也一定大于等于ai,因为我们建立的是一个单调队列。假设有a1<a2,那么根据第一步,a1被清掉,再次加入一个a3,而且a3<a2,那么此时栈有:a2,a3。再加入一个a4<a3,那么a4也只能入栈,栈里的元素,均大于a4,while也就没必要继续了。

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+10,maxn2=31*maxn;
int st[maxn],tt,n,a[maxn],b[maxn];
stack<pair<int,int> > s;
struct node
{
    int x,id;
}h[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&a[i]>s.top().first)
        {
            b[s.top().second]=i;
            s.pop();
        }
        s.push(make_pair(a[i],i));
    }
    for(int i=1;i<=n;i++)
    {
        cout<<b[i]<<endl;  
    }
}

 

Acwing 600. 仰视奶牛(stack记录成对数写法)(每头奶牛的最近仰视对象)

上一篇:delphi – 保持beforepost事件中的值到afterpost事件


下一篇:加载等待蒙版----------WinForm控件开发系列