题目描述

给定一个序列$A$，求出对于每个元素$A[i]$，$\min\limits^{i< j\le n}_{A[j]>A[i]}j$

样例

输入数据

6 
3 
2 
6 
1 
1 
2 

输出数据

3 
3 
0 
6 
6 
0 

算法1

(枚举) $O(n^2)$

思路：

我们可以考虑从小到大枚举任意的两个点$i, j(i < j)$：

如果找到了一个$j$，使得$a[i] < a[j]$，那么可以break掉，进行下一层的枚举。

时间复杂度分析：

显然，枚举i需要$n$次；

而对应每个i，枚举j需要$n - i$次；

所以时间复杂度是$O(n^2)$的。

C++ 代码

int main()
{
    n = read();
    for(rgi i = 1; i <= n; ++i)
        a[i] = read();
    for(rgi i = 1; i <= n; ++i)
        for(rgi j = i + 1; j <= n; ++j)
            if(a[j] > a[i])
            {
                out[i] = j;
                break;
            }
    for(rgi i = 1; i <= n; ++i)
        printf("%d\n", out[i]);
    return 0;
}

算法2

(单调栈) $O(n)$

思路：

我们注意到，被仰视的奶牛的身高一定是单调不递减的，于是我们就可以用一个单调栈来维护。

在枚举每个奶牛的时候，我们可以比较当前奶牛的升高与栈顶的奶牛的身高

如果当前奶牛的身高$>$栈顶奶牛的身高，那么再见了，栈顶的奶牛，以后的任意一个奶牛都不会仰视你了，

因为当前的奶牛一定是更优解；

如果当前奶牛的身高$<$栈顶奶牛的身高，那么就没什么事，压进栈里就好了。

时间复杂度分析：

显然，每个奶牛都只会进出栈$1$次，

所以时间复杂度是$O(n)$的。

C++ 代码

struct node
{
    int id, val;
};

int main()
{
    n = read();
    for(rgi i = 1; i <= n; ++i)
        a[i] = read();
    for(rgi i = 1; i <= n; ++i)
    {
        struct node tmp;
        tmp.id = i, tmp.val = a[i];
        while(!stk.empty() && tmp.val > stk.top().val)
        {
            out[stk.top().id] = i;
            stk.pop();
        }
        stk.push(tmp);
    }
    for(rgi i = 1; i <= n; ++i)
        printf("%d\n", out[i]);
    return 0;
}