Chương trình tìm tòa nhà quan sát được biển Python

Cho mảng heights độ cao các tòa nhà. Tòa nhà ở chỉ số i nhìn thấy biển nếu tất cả tòa nhà bên phải (chỉ số lớn hơn) đều thấp hơn. Trả về danh sách chỉ số có thể nhìn thấy biển theo thứ tự tăng dần.

Ví dụ: heights=[8,12,12,9,10,6] → [2,4,5] (tòa 12 tại chỉ số 2, tòa 10 tại chỉ số 4, tòa cuối cùng).

Giải thuật (Stack đơn điệu)

1. Duyệt từ trái sang phải, duy trì stack chỉ số tòa nhà giảm dần theo chiều cao
2. Với tòa nhà mới h: pop stack trong khi heights[stack[-1]] <= h
3. Push chỉ số hiện tại vào stack
4. Stack cuối cùng chứa chỉ số các tòa nhìn thấy biển (đã sắp xếp tăng dần)

Ví dụ triển khai

def solve(heights):
    stack = []
    for idx, h in enumerate(heights):
        while stack and heights[stack[-1]] <= h:
            stack.pop()
        stack.append(idx)
    return stack

print(solve([8, 12, 12, 9, 10, 6]))

Đầu vào

[8, 12, 12, 9, 10, 6]

Đầu ra

[2, 4, 5]