📌 Problem.

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

한 건물의 옥상에 올라가서 볼 수 있는 다른 건물들에 대해 조사한다.
현재 건물의 높이보다 큰 곳의 건물들만 볼 수 있다.
각 건물 옥상에서 볼 수 있는 다른 건물들의 개수와 그중 가장 가까운 건물을 구하는 문제이다.

📌 Solution.

import sys

input = sys.stdin.readline
N = int(input())
data = list(enumerate(map(int, input().split()), start=1))
count = [0] * (N + 1)
nearest = [float("inf")] * (N + 1)


def solution(buildings):
    visibles = []  # stack

    for idx, height in buildings:
        while visibles and visibles[-1][1] <= height:
            visibles.pop()

        count[idx] += len(visibles)
        if visibles and abs(visibles[-1][0] - idx) < abs(nearest[idx] - idx):
            nearest[idx] = visibles[-1][0]

        visibles.append((idx, height))


# main
solution(data[:])
solution(data[::-1])

for i in range(1, N + 1):
    if count[i] == 0:
        print(count[i])
    else:
        print(count[i], nearest[i])

각 건물들을 총 2번 순회한다.
먼저 1번째 건물부터 N번째 건물까지 순회하며 왼쪽에 보이는 건물들의 정보를 얻는다.
그 뒤 N번째 건물부터 1번째 건물까지 거꾸로 순회하며 오른쪽에 보이는 건물들의 정보를 얻는다.

각 건물을 방문할 때마다 스택에 해당 건물을 push할 것이다.
push하기 전에, 스택에 남아 있는 건물들 중 현재 건물보다 높이가 낮은 건물들은 모두 pop하여 현재 건물에서 보이는 건물들의 정보들을 얻는 것이 핵심이다.

가령 visibles의 상태가 [10, 7, 3, 2]이고 현재 건물의 높이가 5라고 할 때, 높이가 2와 3인 건물을 pop해야 현재 건물에서 볼 수 있는 건물들만 스택에 남게 된다.
따라서 pop 연산 이후 스택 [10, 7]의 크기 2가, 현재 건물에서 보이는 왼쪽(첫번째 순회) 또는 오른쪽(두번째 순회) 건물들의 개수일 것이다.
그리고 스택의 맨위에 남아 있는 높이 7의 건물이, 현재 건물에서 볼 수 있는 가장 가까운 건물일 것이다.

참고로, 첫번째 순회든 두번째 순회든, 스택의 상태는 bottom에서 top까지 늘 내림차순을 유지할 것이다.