Giá Trị Lớn Thứ Hai

Đề bài

Trả về giá trị khác nhau lớn thứ hai trong danh sách. Các giá trị lặp lại chỉ tính một lần.

Cài đặt hàm second_largest(numbers).

numbers: Một danh sách các số nguyên không âm.

Trả về giá trị khác nhau lớn thứ hai, hoặc -1 nếu không tồn tại.

0 ≤ độ dài ≤ 100.000; 0 ≤ mỗi giá trị ≤ 10⁹

Ví dụ 1

Đầu vào:
numbers = [4, 9, 7, 9]

Kết quả mong đợi:
expected = 7

Đầu vào:
std::vector<long long> numbers = {4, 9, 7, 9};

Kết quả mong đợi:
long long expected = 7;

Đầu vào:
long[] numbers = new long[] {4, 9, 7, 9};

Kết quả mong đợi:
long expected = 7;

Các giá trị khác nhau là 9, 7, 4; giá trị lớn thứ hai là 7.

Ví dụ 2

Đầu vào:
numbers = [5, 5]

Kết quả mong đợi:
expected = -1

Đầu vào:
std::vector<long long> numbers = {5, 5};

Kết quả mong đợi:
long long expected = -1;

Đầu vào:
long[] numbers = new long[] {5, 5};

Kết quả mong đợi:
long expected = -1;

Chỉ có một giá trị khác nhau, nên kết quả là -1.

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Bạn cần giá trị lớn nhất và giá trị khác lớn thứ hai, không chỉ hai vị trí đầu.

Gợi ý 2

Theo dõi hai giá trị lớn nhất khác nhau khi duyệt, cập nhật khi một giá trị mới nằm trên hoặc giữa chúng.

Gợi ý 3

Nếu không bao giờ có giá trị khác thứ hai, trả về giá trị dự phòng đặc biệt.

Độ phức tạp mong đợi

thời gian O(n), bộ nhớ phụ O(1)

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.