Đề bài
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.
Ràng buộc
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
Ví dụ
Đầu vào:
numbers = [4, 2, 5, 3]
Kết quả mong đợi:
expected = [0, 0, 2, 2]Đầu vào:
std::vector<long long> numbers = {4, 2, 5, 3};
Kết quả mong đợi:
std::vector<long long> expected = {0, 0, 2, 2};Đầu vào:
long[] numbers = new long[] {4, 2, 5, 3};
Kết quả mong đợi:
long[] expected = new long[] {0, 0, 2, 2};Giải thích
4 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 2.
Đầu vào:
numbers = [2, 2, 2]
Kết quả mong đợi:
expected = [0, 0, 0]Đầu vào:
std::vector<long long> numbers = {2, 2, 2};
Kết quả mong đợi:
std::vector<long long> expected = {0, 0, 0};Đầu vào:
long[] numbers = new long[] {2, 2, 2};
Kết quả mong đợi:
long[] expected = new long[] {0, 0, 0};Giải thích
Earlier equal values are not strictly smaller. Every answer is 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Với mỗi vị trí, bạn cần giá trị gần nhất phía trước mà nhỏ hơn строго, không phải nhỏ hơn hoặc bằng.
Gợi ý 2
Duy trì monotonic stack chứa các ứng viên cùng vị trí khi quét từ trái sang phải.
Gợi ý 3
Pop các giá trị bằng hoặc lớn hơn, vì chúng không bao giờ là đáp án nhỏ hơn gần nhất cho phần tử sau.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.