การค้นหาสี่เหลี่ยมผืนผ้าใหญ่ที่สุด: อธิบายปัญหาสี่เหลี่ยมผืนผ้าสูงสุด

ในสาขาของเรขาคณิตและอัลกอริธึม ปัญหาสี่เหลี่ยมผืนผ้าสูงสุดถือเป็นความท้าทายที่น่าสนใจ มันถามว่าเราจะสามารถหาสี่เหลี่ยมผืนผ้าที่มีพื้นที่มากที่สุดซึ่งสามารถวาดอยู่ภายในกริดที่มีพื้นที่เต็มและว่างได้อย่างมีประสิทธิภาพอย่างไร ปัญหานี้มีความหมายแท้จริงในโครงการต่างๆ เช่น การกำหนดตำแหน่งหน้าต่างในงานออกแบบ UI ทำให้เป็นสิ่งที่จำเป็นสำหรับนักพัฒนาและนักออกแบบที่จะต้องเข้าใจและนำเสนอวิธีแก้ไข

คำอธิบายของปัญหา

ลองจินตนาการถึงกริดที่แทนที่หน้าจอ โดยที่:

• พื้นที่ที่เต็มไปนั้นใช้ตัวอักษร '#' แสดง
• พื้นที่ว่างแสดงโดยจุด '.'

จากการแทนที่ดังกล่าว ภารกิจคือการระบุสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดซึ่งประกอบขึ้นจาก '.' ทั้งหมดในพื้นที่เต็มข้างต้น ตัวอย่างของกริดอาจมีลักษณะเป็นดังนี้:

....................
..............######
##..................
.................###
.................###
#####...............
#####............... 
#####...............

ตามที่คุณเห็น เป้าหมายคือการคำนวณพื้นที่ของพื้นที่ว่างที่ต่อเนื่องกันมากที่สุดในพื้นที่ที่เต็มไปด้วยข้อมูล

การเข้าใจวิธีแก้ปัญหา

เพื่อจัดการกับปัญหาสี่เหลี่ยมผืนผ้าสูงสุด เราสามารถนำนำหลักการจากปัญหาที่มีชื่อเสียงอื่น ๆ โดยเฉพาะปัญหาฮิสโตแกรม กลยุทธ์หลักคือการเปลี่ยนกริดของเราให้อยู่ในรูปแบบของฮิสโตแกรมหลายชุด แล้วคำนวณพื้นที่จากโครงสร้างเหล่านี้ วิธีการแบ่งออกได้ดังนี้:

1. การแทนค่าของแถวเป็นฮิสโตแกรม

สำหรับแต่ละแถวในกริด เราสามารถคำนวณอาเรย์ความสูงที่แสดงถึงความสูงของสี่เหลี่ยมว่างที่ต่อเนื่องกันซึ่งสิ้นสุดที่แถวดังกล่าว โดยหลักการคือ:

• หากองค์ประกอบในกริดคือ '.' ให้เพิ่มความสูงจากแถวด้านบน
• หากมันเป็น '#' ให้รีเซ็ตความสูงกลับเป็นศูนย์

2. การคำนวณพื้นที่สี่เหลี่ยมผืนผ้าสำหรับแต่ละแถว

เมื่อเรามีอาเรย์ความสูงสำหรับแต่ละแถวแล้ว ขั้นตอนถัดไปคือการคำนวณพื้นที่ของสี่เหลี่ยมผืนผ้าขนาดใหญ่ที่สุดที่สามารถจัดรูปได้จากอาเรย์ความสูงนี้ซึ่งสามารถทำได้อย่างมีประสิทธิภาพโดยใช้โครงสร้างข้อมูลสแต็ก:

• เดินผ่านอาเรย์ความสูง
• ใช้สแต็กเพื่อติดตามดรรชนีของบาร์
• เมื่อพบบาร์ที่ต่ำกว่า ให้ป๊อปจากสแต็กเพื่อกำหนดความสูงและคำนวณพื้นที่ โดยอัปเดตพื้นที่สูงสุดที่พบจนถึงขณะนั้น

3. ภาพรวมของการดำเนินการ

เพื่อดำเนินการอัลกอริธึมอย่างมีประสิทธิภาพ โปรดทำตามขั้นตอนเหล่านี้:

• เริ่มต้นอาเรย์ความสูงเพื่อเก็บความสูงสำหรับแต่ละคอลัมน์
• ทำซ้ำผ่านแต่ละแถวของกริด
• อัปเดตอาเรย์ความสูงตามองค์ประกอบของแถวดังกล่าว
• ใช้วิธีการสแต็กเพื่อตรวจสอบพื้นที่สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดสำหรับการตั้งค่าความสูงในปัจจุบัน

ตัวอย่างโค้ด

นี่คือตัวอย่างโค้ด Python ที่เรียบง่ายเพื่อแสดงกระบวนการนี้:

def maximalRectangle(matrix):
    if not matrix:
        return 0

    height = [0] * len(matrix[0])
    max_area = 0

    for row in matrix:
        for i in range(len(row)):
            height[i] = height[i] + 1 if row[i] == '.' else 0
        max_area = max(max_area, largestRectangleArea(height))
    return max_area

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

บทสรุป

ปัญหาสี่เหลี่ยมผื่นผ้าสูงสุดไม่เพียงแต่มอบความท้าทายที่น่าสนใจสำหรับผู้ที่ชื่นชอบอัลกอริธึมเท่านั้น แต่ยังมีแอปพลิเคชันที่สำคัญในโลกจริงอีกด้วย ด้วยการแทนปัญหาอย่างมีประสิทธิภาพโดยใช้ฮิสโตแกรมและการใช้สแต็กในการคำนวณพื้นที่ เราสามารถแก้ไขมันได้ในเวลาเชิงเส้น

สำหรับการอ่านเพิ่มเติมและข้อมูลเชิงลึก โปรดพิจารณาบทความที่ละเอียดจาก Dr. Dobb’s Journal ที่กล่าวถึงโดย @lassevk ซึ่งสามารถดูได้ที่ นี่ ด้วยความรู้เกี่ยวกับอัลกอริธึมนี้ คุณสามารถแก้ไขปัญหาที่คล้ายกันที่เกิดขึ้นในโครงการของคุณได้อย่างมั่นใจ

อย่างที่รู้กันดี ความสำคัญที่แท้จริงในการเชี่ยวชาญอัลกอริธึมคือการฝึกฝน! ดังนั้นลองนำวิธีแก้ไขนี้ไปใช้ในภาษาโปรแกรมที่คุณชื่นชอบและดูว่ามันทำงานได้ดีเพียงใดสำหรับการตั้งค่ากริดที่แตกต่างกัน