Max Stack

• Reference
• Stack의 기능 top, push_back, pop_back 뿐만 아니라 max 값을 찾아서 주는 기능도 추가하는 문제다.

Algorithm

[ 1 3 3 2 2 5 1 ]

• 위와 같은 Input이 Stack에 들어간다고 해보자.
• 이는 max기능의 Time Complexity를 O(1)로 만들기 위해 Space Complexity를 조금 손해본다. 두 개의 Stack을 만드는 것이다. 하나는 원래 Stack 기능, 하나는 Max를 위한 Stack 이다.

Stack	Max (elem, count)
1	1,1
3	3,1
3	3,2
2	3,2
2	3,2
5	5,1
1	5,1

• Max Stack은 반복되는 지점은 그냥 push 안한다고 보면된다. 즉, 들어오는 원소가 기존 원래 있떤 원소보다 크면 Update, 같으면 개수를 Update 해준다.
• Max 기능을 요청하면 Max Stack의 top을 사용하여 O(1)로 max 값을 제공할 수 있다.