문제
generic Stack<T>는 어떤 타입에도 사용할 수 있습니다. 여기서는 그 개념을 확장하여, 정수 스택이면서 최소값도 constant time에 보고할 수 있게 합니다.
연산을 순서대로 처리하세요:
push <x>: x를 push합니다.pop: 맨 위 값을 제거합니다(스택이 비어 있으면 무시됩니다).min: 현재 스택의 가장 작은 값을 보고하거나, 비어 있으면 -1을 반환합니다.
min_stack_operations(operations)를 구현하세요.
Input
operations: 연산들.
Output
min 연산들의 답을 순서대로 반환하세요.
제약 조건
1 ≤ 연산 수 ≤ 200,000
0 ≤ x ≤ 10^9
예시
예시 1
입력:
operations = ["push 5", "push 3", "min", "pop", "min"]
예상 출력:
expected = [3, 5]입력:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
예상 출력:
std::vector<long long> expected = {3, 5};입력:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
예상 출력:
long[] expected = new long[] {3, 5};설명
5와 3이 스택에 있을 때 최소값은 3입니다. 3을 pop한 뒤에는 5만 남습니다: [3, 5].
예시 2
입력:
operations = ["min", "pop", "push 7", "min"]
예상 출력:
expected = [-1, 7]입력:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
예상 출력:
std::vector<long long> expected = {-1, 7};입력:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
예상 출력:
long[] expected = new long[] {-1, 7};설명
비어 있는 스택은 -1을 보고하고 pop은 무시됩니다. 그다음 최소값은 7입니다: [-1, 7].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 값 옆에 그 시점의 스택 최솟값을 저장하세요.
힌트 2
그러면 현재 최솟값은 두 번째 스택의 맨 위 값입니다.
힌트 3
빈 스택의 pop은 무시하고, 비어 있을 때 min은 -1을 반환하세요.
예상 복잡도
시간 O(연산 수), 추가 공간 O(연산 수)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.