Giả sử chúng ta có một danh sách chỉ chứa 0 và 1 gọi là seats. Trong đó seats[i] đại diện cho một ghế. Khi là 1, ghế đó đã được ngồi, ngược lại trống. Có ít nhất một ghế trống và một ghế đã ngồi, chúng ta phải tìm khoảng cách lớn nhất từ một ghế trống đến ghế đã ngồi gần nhất.
Vì vậy, nếu đầu vào là seats = [1, 0, 1, 0, 0, 0, 1], thì đầu ra sẽ là 2, vì ta có thể ngồi ở seats[4], khi đó khoảng cách là 2.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:
res := 0
last := -1
n := kích thước seats
với i từ 0 đến n - 1, thực hiện
nếu seats[i] là 1, thì
res := max(res, i nếu last < 0 ngược lại (i - last) // 2)
last := i
trả về max(res, n - last - 1)
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
def solve(seats):
res, last, n = 0, -1, len(seats)
for i in range(n):
if seats[i]:
res = max(res, i if last < 0 else (i - last) // 2)
last = i
return max(res, n - last - 1)
seats = [1, 0, 1, 0, 0, 0, 1]
print(solve(seats))
Đầu vào
[1, 0, 1, 0, 0, 0, 1]
Đầu ra
2