EOJ 3213 向右看齐

题目描述

N 头奶牛被紧急动员起来了，它们排成了一条长列。从左向右看，排在第 i 个位置的奶牛身高为 Hi。约翰一声令下，所有奶牛向右看齐。假设每头奶牛只能看到比自己高的牛。请问它们各自看到的最近的一头奶牛分别是谁呢？
Input

第一行：单个整数 N，1≤N≤10⁶

第二行到 N+1 行：第 i+1 行有一个整数 Hi，1≤Hi≤10⁶
Output

第一行到第 N 行：第 i 行有一个整数 Ci，表示第 i 头奶牛向右看到的最近的一头奶牛编号，如果看不到任何奶牛，Ci 为 0。

一开始用朴素的循环遍历算法，如果单调递减，复杂度是O(n²)，显然是不可行的。

听同学讲解后才知道是单调栈，具体见转载的相关博客。

C语言实现

 1 #include  <stdio.h>
 2 #define N 100010
 3 int main()
 4 {
 5     int n;scanf("%d",&n);
 6     int h[N],ans[N];
 7     for(int i=1; i<=n; i++)  scanf("%d",&h[i]);
 8     ans[n]=0;
 9     for(int i=n-1; i>=1; i--)
10     {
11         if(h[i]<h[i+1]) ans[i]=i+1;
12         else if(h[i]==h[i+1])ans[i]=ans[i+1];
13         else
14         {
15             int j=i;
16             for(;h[i]>=h[ans[j+1]];j++)
17                 if(ans[j+1]==0) break;
18             ans[i]=ans[j+1];
19         }
20     }
21     for(int i=1; i<=n; i++)
22         printf("%d
",ans[i]);
23 
24 }是

细读就可以理解含义，最后一头奶牛向右没有，编号是0，依次向前遍历，对于奶牛i，如果高度低于后一头i+1，那么编号i+1，如果高度相同，后一头能看到的最近的奶牛也必然是i能看到的奶牛，故编号为ans[i+1]，当高度高于前一头奶牛，就需要向后遍历直到后面的最高的奶牛。显然，这不是单调栈。(逃

并且在第三种情况下，时间复杂度略高。

以下是单调栈的写法，实现语言C++

 1 #include <iostream>
 2 #include <stack>
 3 #define N 1000001
 4 using namespace std;
 5 int main()
 6 {
 7     stack<pair<int,int> > s;
 8     int T,tmp;cin>>T;
 9     int ans[N];
10     for(int m=1;m<=T;m++){
11         cin>>tmp;
12         if(!s.empty())
13             while(!s.empty()&&s.top().first<tmp){
14                 ans[s.top().second]=m;
15                 s.pop();
16             }
17         s.push(make_pair(tmp,m));
18     }
19     while(!s.empty()){
20         ans[s.top().second]=0;
21         s.pop();
22     }
23     for(int i=1;i<=T;i++) cout<< ans[i] <<endl;
24     return 0;
25 }

还用一种更快(一点点)的是额外开一个数组记录读取的数字，stack只需要记录下标，或者反过来，总之原理是一样的。