모노토닉 스택(monotonic stack)을 이용한 나보다 큰 첫 번째 수 찾기 문제(오큰수,NGE,next greater element)

1. 모노토닉 스택(monotonic stack) 스택 내부의 원소들을 항상 오름차순, 혹은 내림차순 상태를 유지하도록 만드는 자료구조 나보다 크거나, 작은 숫자가 언제 처음 나오는지를 찾는데 유용하다. 알고리즘 문제에서 보통, "배열에서 나보다 크면서 오른쪽에 있는 수 중 첫번째 수는?" 예를 들어, [5,3,1,4,2]가 있다고 하자. 각 숫자에 대해서 "오른쪽에 있는 나보다 큰 첫번째 수"들을 모두 O(N)에 찾으라고 한다면? 스택 []을 두고, 왼쪽부터 오른쪽 차례대로 순회한다. 스택이 비어있으니까 [5] 2번째 3이 들어오는데, 스택의 마지막 수 5가 3보다 더 크므로 그대로 입장 [5,3] 3번째 1이 들어오는데 스택의 마지막 수 3이 1보다 더 크므로 [5,3,1] 4번째 4가 들어오는데 ..