Bài toán
Link đến bài toán: 1503. Last Moment Before All Ants Fall Out of a Plank
Phân tích
Như mấy bài trong tuần này, bài này khó nhất là hiểu được đề bài. Đề bài có một chi tiết rằng, khi hai con kiến gặp nhau, chúng sẽ đổi hướng đi. Nhưng, nếu ta để ý kĩ thì hai con kiến có đổi hướng hay không thì tổng quãng đường mà chúng đi vẫn là như cũ. Vậy nên đây là 1 chi tiết đánh lạc hướng, ta bỏ qua chi tiết này thì ta nhận thấy rằng thời gian mà đề bài yêu cầu là thời gian lớn nhất mà một con kiến đi được.
Giải thuật
- Khởi tạo một biến
maxDistance
để lưu giá trị lớn nhất của khoảng cách mà một con kiến đi được. - Duyệt mảng
right
và tìm khoảng cách lớn nhất mà một con kiến đi được, tức làn - v
(v là giá trị của phần tử hiện tại). - Duyệt mảng
left
và tìm khoảng cách lớn nhất mà một con kiến đi được, tức làv
(v là giá trị của phần tử hiện tại). - Trả về
maxDistance
.
func getLastMoment(n int, left []int, right []int) int {
maxDistance := 0
for _, v := range right {
maxDistance = max(maxDistance, n-v)
}
for _, v := range left {
maxDistance = max(maxDistance, v)
}
return maxDistance
}