[연산] 아마존 인터뷰 : 최소 스택

이를 구현하는 한 가지 방법은 스택의 일부 요소 아래에있는 모든 값의 최소값을 추적하는 것입니다.
스택의 모든 요소에 대해 실제로 2 개의 요소가 있습니다. 하나는 실제 값이고 그 위에는 그 아래에있는 모든 요소의 최소값입니다.

1. 푸시-새 값을 상단 최소값과 비교하고 값과 현재 최소값을 모두 푸시합니다.
2. 팝-스택에서 두 번만 팝합니다 (값과 현재 최소값 모두).
3. Min-스택의 맨 위를 반환합니다.

예 : 요소 7, 9, 3, 5, 1, 2(이 순서)의 경우 스택은 다음과 같습니다.

TOP:    1 <--- min(7,9,3,5,1,2)
        2
                1 <--- min(7,9,3,5,1)
                        1
                                3 <--- min(7,9,3,5)
                                        5
                                                3 <--- min(7,9,3)
                                                        3
                                                                7 <--- min(7,9)
                                                                        9
                                                                                7 <--- min(7)
                                                                                        7
                                                                                        

-------------------

솔루션은 간단하고 우아합니다. 추가 스택을 사용하여 최소값을 유지하십시오.

1.To retrieve the current minimum, just return the top element from minimum stack.
2.Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack
too.
3.When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum
stack too.

-------------------

일반 스택의 각 값을 2 개의 요소가있는 벡터로 만듭니다. 여기서 첫 번째 요소는 값을 나타내고 두 번째 요소는 최소 실행 값을 나타냅니다.

래핑 메서드는 벡터를 마스킹 할 수 있으므로 인터페이스 및 서명에서 일반 값만 사용할 수 있습니다.

출처
https://stackoverflow.com/questions/39940165