仰视奶牛

题目 仰视奶牛

image-170b530e

思路分析

找右边的最近的较大的数

模板变形成

从右开始找

因为找较大的 所以栈里应该是单调递减的 这样栈头才会是最优解

所以如果出现往上走的趋势 就出栈

image-6eb4c58b

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int h[N],s[N],ans[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>h[i];

    int top=1;

    for(int i=n;i>=1;i--){

        while(top>0 && h[i]>=h[s[top]])

            top--;

        ans[i]=s[top];

        s[++top]=i;

    }

    for(int i=1;i<=n;i++)

        cout<<ans[i]<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 单调栈 🏠 00-刷题理模型 ➡️ 单调栈