Cho mảng nums và kích thước cửa sổ trượt k. Tìm giá trị lớn nhất trong mỗi cửa sổ trượt theo thời gian tuyến tính O(n).
Ví dụ: nums = [1,3,-1,-3,5,3,6,7], k = 3 -> [3,3,5,5,6,7]
Định Dạng Đầu Vào (Input)
Dòng 1: Mảng nums
Dòng 2: Số nguyên k
Dòng 2: Số nguyên k
Định Dạng Đầu Ra (Output)
Mảng chứa các giá trị lớn nhất
Ràng Buộc (Constraints)
1 <= nums.length <= 10^5
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1,3,-1,-3,5,3,6,7]
3
Output:
[3,3,5,5,6,7]
Giải thích: Max từng bước
Ví dụ 2:
Input:
[1]
1
Output:
[1]
Giải thích: Cửa sổ 1
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Monotonic Deque O(n)
Dùng Deque lưu index giảm dần giá trị. Đầu Deque luôn là max của cửa sổ hiện tại.
Dữ liệu đầu vào (Input):
[1,3,-1,-3,5,3,6,7]
3
Kết quả kỳ vọng (Expected Output):
[3,3,5,5,6,7]
Dữ liệu đầu vào (Input):
[1]
1
Kết quả kỳ vọng (Expected Output):
[1]
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
