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

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

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

ขั้นตอนการแก้ปัญหา

1. stack := รายการใหม่
2. สำหรับแต่ละดัชนี idx และความสูง h ใน heights:
   • ในขณะที่ stack ไม่ว่าง และ heights[stack[-1]] <= h:
     • ลบสมาชิกสุดท้ายออกจาก stack
   • เพิ่ม idx เข้า stack
3. คืนค่า stack

ตัวอย่างการใช้งาน

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]