Chương trình tìm các tòa nhà từ nơi có thể nhìn thấy biển bằng Python

Giả sử chúng ta có một danh sách các chiều cao của các tòa nhà khác nhau. Một tòa nhà có giá trị heights [i] có thể nhìn thấy đại dương khi mọi tòa nhà ở bên phải của nó đều ngắn hơn tòa nhà đó. Chúng tôi phải tìm các chỉ số của tòa nhà từ nơi chúng tôi có thể nhìn thấy đại dương, theo thứ tự tăng dần.

Vì vậy, nếu đầu vào giống như heights =[8, 12, 12, 9, 10, 6], thì đầu ra sẽ là [2, 4, 5] vì chúng ta có thể nhìn thấy đại dương từ việc xây dựng độ cao 12 ở chỉ mục 2, từ chiều cao tòa nhà 10 ở chỉ số 10 và từ tòa nhà cuối cùng ở chỉ số 5. ​​

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• stack:=một danh sách mới
• đối với mỗi idx chỉ mục và chiều cao h tính theo chiều cao, hãy thực hiện
  • trong khi ngăn xếp không trống và chiều cao [đầu ngăn xếp] <=h, thực hiện
    • xóa phần tử cuối cùng khỏi ngăn xếp
• đẩy idx vào ngăn xếp
• trả về ngăn xếp

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

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

Đầu vào

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

Đầu ra

[2, 4, 5]