2493번: 탑

https://www.acmicpc.net/problem/2493


$O(n)$

새로운 탑 정보를 스택에 추가할 때마다 기존 스택에 있는 현재 탑보다 작은 탑을 모두 pop시킨다.
탑을 추가할 때마다 이러한 작업을 한 뒤에 스택의 가장 위에 있는 탑 번호를 출력하고 스택에 현재 탑을 추가한다.
이러한 방식을 유지하면 탑이 높이를 기준으로 내림차순 정렬된다.

#include<cstdio>
int a[500000] = { 0x7fffffff }, stk[500000], top, n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        while (a[stk[top]] < a[i]) top--;
        printf("%d ", stk[top]);
        stk[++top] = i;
    }
    return 0;
}