โปรแกรมค้นหาอาคารที่สามารถมองเห็นทะเลได้ใน Python

สมมติว่าเรามีรายการความสูงของอาคารต่างๆ อาคารที่มีความสูง มีค่าความสูง[i] สามารถมองเห็นมหาสมุทรได้เมื่อทุกอาคารทางด้านขวาจะสั้นกว่าอาคารนั้น เราต้องหาดัชนีอาคารจากจุดที่มองเห็นมหาสมุทรเป็นลำดับจากน้อยไปมาก

ดังนั้นหากอินพุตเท่ากับความสูง =[8, 12, 12, 9, 10, 6] แล้วผลลัพธ์จะเป็น [2, 4, 5] เพราะเราสามารถเห็นมหาสมุทรจากความสูงของอาคาร 12 ที่ดัชนี 2 จาก ความสูงของอาคาร 10 ที่ดัชนี 10 และจากอาคารสุดท้ายที่ดัชนี 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• stack :=รายการใหม่
• สำหรับแต่ละดัชนี idx และความสูง h ในความสูง ทำ
  • ในขณะที่ stack ไม่ว่างและ heights[top of stack ] <=h do
    • ลบองค์ประกอบสุดท้ายออกจากสแต็ก
• พุช idx ลงในสแต็ก
• ส่งคืนสแต็ก

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

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

ผลลัพธ์

[2, 4, 5]