猴子向右看，FOJ上某题 单调栈

N (1 <= N <= 100,000) monkeys in the mountains, conveniently numbered 1..N, are once again standing in a row. Monkey i has height H_i (1 <= H_i <= 1,000,000).

Each monkey is looking to his left toward those with higher index numbers. We say that monkey i "looks up" to monkey j if i < j and H_i< H_j. For each monkey i, we would like to know the index of the first monkey in line looked up to by monkey i.

题意：告诉n个一排猴子，每个猴子向右看，问第一个比自己高的猴子的位置，没有就输出0，最后一个也是0

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>
#define N 100009
using namespace std;

int a[N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }

        int ans[N];
        memset(ans,0,sizeof ans);
        ans[n]=n;//初始化为n，但是实际值为0
        for(int i=n-1;i>=1;i--)//找右边第一个比a[i]小的位置
        {
            int tt=i;
            while(tt<n&&a[i]>=a[tt+1]) tt=ans[tt+1];
            ans[i]=tt;
        }

        for(int i=1;i<n;i++)
        {
            if(ans[i]==n)//当是最后一个猴子的时候，并不一定保证比当前猴子高
            if(a[i]<a[n])
            printf("%d\n",ans[i]+1);
            else
            cout<<0<<endl;
            else
            printf("%d\n",ans[i]+1);

        }

        cout<<0<<endl;

    }
    return 0;
}

猴子向右看，FOJ上某题 单调栈

原文：http://blog.csdn.net/wust_zjx/article/details/46778103