Tìm phần tử lớn hơn tiếp theo bằng Monotonic Stack
Cho mảng số nguyên nums. Với mỗi vị trí i, phần tử lớn hơn tiếp theo là phần tử đầu tiên nằm sau nó có giá trị lớn hơn nums[i]. Nếu không có phần tử nào lớn hơn, kết quả là -1.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: stack, loops.
Nội dung đề bài
Mục tiêu kiến thức
- Sử dụng ngăn xếp đơn điệu giảm (Monotonic Decreasing Stack) để tìm kiếm phần tử lớn hơn đầu tiên bên phải.
- Xử lý mảng vòng tròn (Circular Array) bằng toán tử modulo
% N. - Tối ưu hóa thời gian thực thi từ O(N2) xuống O(N).
Mô tả bài toán
Cho mảng số nguyên nums. Với mỗi vị trí i, phần tử lớn hơn tiếp theo là phần tử đầu tiên nằm sau nó có giá trị lớn hơn nums[i]. Nếu không có phần tử nào lớn hơn, kết quả là -1.
Viết hàm next_greater_elements(nums: list[int], circular: bool = False) -> list[int]:
- Nếu
circular=False: Chỉ tìm kiếm phần tử bên phải đến hết mảng. - Nếu
circular=True: Mảng được coi là một vòng tròn, tìm kiếm tiếp tục vòng lại từ đầu mảng cho tới trước vị trí hiện tại. - Thuật toán phải sử dụng monotonic stack để đạt độ phức tạp O(N).
Input
- Tham số:
nums: list[int],circular: bool.
Output
- Trả về:
list[int].
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
next_greater_elements([1, 2, 1], False)Output
[2, -1, -1]Giải thích
Hàm được gọi với các tham số mẫu trên và trả về kết quả chính xác theo yêu cầu.
Ví dụ 2
Input
next_greater_elements([1, 2, 1], True)Output
[2, -1, 2]Giải thích
Hàm được gọi với bộ tham số thứ hai và trả về kết quả tương ứng theo thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.