[TIOJ][Stack] 1176 Cows

Cows

Time Limit:7000MS  Memory Limit:65536K
Total Submit:428 Accepted:171
Case Time Limit:4000MS

Description

給定一排牛(不是一牛排)每頭牛的高度，牠們只能往右平視或俯視，請問牠們分別能夠看到幾頭牛？
(如果兩頭牛的高度一樣，那麼左邊的牛的視野只能看到右邊的牛為止。)

Input

第一列有正整數N(1<=N<=1,000,000)
第2～N+1列各有一個正整數，依序代表由左而右的牛隻高度。所有數字都會在int範圍。

Output

每一列分別輸出一個整數，代表由左而右每頭牛所能看見的牛隻數量。
請注意：最後一列一定會輸出0。

Sample Input

5
1
2
3
4
5

Sample Output

1
1
1
1
0

Hint

※額外的測試中，有60%的測試資料當中的 N<=10,000。

Source

TIOJ Contest #1020。Problem Setter：Tmt。
--------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<stack>
using namespace std;
int s[1000005];
int ans[1000005]={0};
stack<int> sta;
int main(){
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&s[i]);
    sta.push(n-1);
    ans[n-1]=0;
    for(i=n-2;i>=0;i--){
        while(sta.size() && s[i]>s[sta.top()]) sta.pop();
        if(sta.size())
            ans[i]=sta.top()-i;
        else ans[i]=n-i-1;
        sta.push(i);
    }
    for(i=0;i<n;i++)
        printf("%d\n",ans[i]);

}