Chương trình tìm tòa nhà có tầm nhìn tốt hơn trong Python

Mô tả bài toán

Cho mảng heights chiều cao các tòa nhà trên một đường thẳng. Tòa nhà có tầm nhìn tốt nếu không bị che khuất bởi tòa nhà cao hơn phía sau (bên phải). Trả về chỉ số các tòa nhà có tầm nhìn tốt.

Ví dụ

Nếu heights = [5, 6, 8, 7], đầu ra là [2, 3]. Tòa nhà 0,1 bị che bởi tòa 2. Tòa 2,3 không bị che.

Giải thuật

1. Duyệt từ phải sang trái, giữ h là chiều cao tối đa đã thấy.
2. Nếu heights[i] > h: thêm i vào kết quả, cập nhật h.
3. Đảo ngược kết quả trước khi trả về.

Triển khai Python

def solve(heights):
    res, h = [], 0
    for i in range(len(heights) - 1, -1, -1):
        if heights[i] > h:
            res.append(i)
            h = heights[i]
    return res[::-1]

print(solve([5, 6, 8, 7]))

Đầu vào

[5, 6, 8, 7]

Đầu ra

[2, 3]