문제
For each number, find the closest earlier position containing a strictly smaller number. Equal numbers do not qualify. Positions start at 1; use 0 when there is no smaller number to the left.
Implement nearest_smaller_value(numbers).
Input
numbers: Numbers in their original order.
Output
Return one earlier position (or 0) for every input value.
제약 조건
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
예시
입력:
numbers = [4, 2, 5, 3]
예상 출력:
expected = [0, 0, 2, 2]입력:
std::vector<long long> numbers = {4, 2, 5, 3};
예상 출력:
std::vector<long long> expected = {0, 0, 2, 2};입력:
long[] numbers = new long[] {4, 2, 5, 3};
예상 출력:
long[] expected = new long[] {0, 0, 2, 2};설명
4 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 2.
입력:
numbers = [2, 2, 2]
예상 출력:
expected = [0, 0, 0]입력:
std::vector<long long> numbers = {2, 2, 2};
예상 출력:
std::vector<long long> expected = {0, 0, 0};입력:
long[] numbers = new long[] {2, 2, 2};
예상 출력:
long[] expected = new long[] {0, 0, 0};설명
Earlier equal values are not strictly smaller. Every answer is 0.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 위치마다 더 작기만 한 가장 가까운 이전 값을 찾아야 하며, 작거나 같은 값은 아닙니다.
힌트 2
왼쪽에서 오른쪽으로 보면서 위치가 함께 들어 있는 단조 스택을 유지하세요.
힌트 3
같거나 더 큰 값은 나중 원소의 가장 가까운 더 작은 값이 될 수 없으므로 pop 하세요.
예상 복잡도
시간 O(n), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.