สมมติว่าเราได้รับคะแนน n เป็น (x, y) พื้นที่แนวตั้งคือพื้นที่ที่ขยายออกไปตามแกน y อย่างไม่สิ้นสุด เราต้องหาพื้นที่แนวตั้งระหว่างจุดสองจุดเพื่อไม่ให้มีจุดอื่นอยู่ภายในพื้นที่และกว้างที่สุด
ดังนั้น หากอินพุตเป็นเหมือน pts =[[10,9],[11,11],[9,6],[11,9]] ผลลัพธ์จะเป็น 1
พื้นที่สีแดงและสีน้ำเงินเหมาะสมที่สุด และไม่มีจุดอยู่ภายใน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เรียงลำดับรายการ pts
-
สำหรับฉันอยู่ในช่วง 1 ถึงขนาดของ pts ทำ
-
ส่งคืนค่าสูงสุดของ (pts[i, 0] - pts[i - 1, 0])
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(pts): pts.sort() return max(pts[i][0] - pts[i - 1][0] for i in range(1, len(pts))) print(solve([[10,9],[11,11],[9,6],[11,9]]))
อินพุต
[[10,9],[11,11],[9,6],[11,9]]
ผลลัพธ์
1
