On this page

ข้อ 18 · LC1732 Find the Highest Altitude (ความสูงมากสุด) 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

ไต่ altitude (ระดับความสูง) ตาม gain ที่ให้มา แล้วหา highest point (จุดสูงสุด) ที่ไปถึง

โจทย์ (LC1732): นักปั่นจักรยานออกทริปบนเส้นทางที่มี n + 1 จุดซึ่งมี altitude (ระดับความสูง) ต่างกัน เริ่มต้นทริปที่จุด 0 ด้วย altitude เท่ากับ 0 กำหนด array จำนวนเต็ม gain ความยาว n โดย gain[i] คือค่าต่างสุทธิของ altitude ระหว่างจุดที่ i กับจุดที่ i + 1 ให้ return altitude ที่สูงที่สุดของจุดใดจุดหนึ่งบนเส้นทางนี้

Example 1

Input:: gain = [-5, 1, 5, 0, -7]
Output:: 1
Explanation:: altitude ตามลำดับจุดคือ [0, -5, -4, 1, 1, -6] ค่าสูงสุดคือ 1

Example 2

Input:: gain = [-4, -3, -2, -1, 4, 3, 2]
Output:: 0
Explanation:: altitude ตามลำดับจุดคือ [0, -4, -7, -9, -10, -6, -3, -1] ค่าสูงสุดคือ 0 ซึ่งเป็นจุดเริ่มต้น

Constraints (ข้อจำกัด)

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

จุดเริ่มต้น altitude 0 นับด้วยเสมอ ถ้า gain ทำให้ altitude ติดลบตลอด คำตอบก็ยังเป็น 0

แนวทาง — ต้องใช้อะไร & คิดยังไง

นี่คือ prefix sum (ผลรวมสะสม) ในรูปแบบพื้นฐานที่สุด altitude ของจุดที่ k ก็คือ prefix sum ของ gain[0..k-1] เพราะแต่ละ gain คือส่วนต่างที่บวกเข้าไปทีละก้อน

วิธี naive (ตรงตัว) คือสร้าง array prefix เก็บทุก altitude แล้วค่อยหา max (ค่ามากสุด) แต่เราไม่ต้องเก็บทั้ง array เลย เพราะต้องการแค่ค่ามากสุด จึง accumulate (บวกสะสม) ในตัวแปรเดียวแล้ว track (จำ) ค่าสูงสุดที่เคยเจอไว้ ประหยัด memory จาก O(n) เหลือ O(1)

initialize (ตั้งค่าเริ่มต้น) altitude = 0 เก็บ altitude ปัจจุบัน (เริ่มที่จุด 0)
initialize highest = 0 เก็บค่าสูงสุดที่เคยไปถึง (จุดเริ่มก็คือ 0)
iterate (วน) ทีละค่า g ใน gain: บวก g เข้า altitude (accumulate)
update highest ให้เป็น max ระหว่าง highest เดิมกับ altitude ล่าสุด
จบ loop แล้ว return highest

จุดพลาดที่พบบ่อย

ลืมนับจุดเริ่มต้นที่ altitude 0 ทำให้ตอบผิดเวลา gain ทำให้ altitude ติดลบทั้งหมด การ initialize highest = 0 ตั้งแต่แรกครอบคลุม edge case (กรณีขอบ) นี้ให้เอง

ไล่ทีละสเต็ป

ลอง iterate gain = [-5, 1, 5, 0, -7] ดูค่าตัวแปรเปลี่ยนทีละรอบ

g	altitude (หลังบวก)	highest
(เริ่มต้น)	0	0
-5	-5	0
1	-4	0
5	1	1
0	1	1
-7	-6	1

จบ loop highest = 1 ตรงกับคำตอบ

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def largest_altitude(gain):
    altitude = 0        # ระดับความสูงปัจจุบัน (เริ่มที่จุด 0)
    highest = 0         # ค่าสูงสุดที่เคยไปถึง (จุดเริ่มก็ 0)
    for g in gain:      # ไล่ค่าต่างระดับทีละก้อน
        altitude += g   # สะสมค่าต่างระดับ = ผลรวมสะสม (prefix sum)
        highest = max(highest, altitude)  # จำค่ามากสุดที่เคยเจอ
    return highest      # คืนจุดสูงสุด

print(largest_altitude([-5, 1, 5, 0, -7]))          # 1
print(largest_altitude([-4, -3, -2, -1, 4, 3, 2]))  # 0

Output

1
0

หัวใจอยู่ที่บรรทัด altitude += g ซึ่งก็คือการสร้าง prefix sum ทีละสเต็ป ตัว altitude ณ รอบใด ๆ คือ altitude จริงของจุดนั้น ถ้าเราอยากได้ทุก altitude ก็เก็บลง array ได้ แต่โจทย์ถามแค่ max จึงเก็บแค่ highest พอ

ถ้าลองเปลี่ยนบรรทัด highest = 0 เป็น highest = altitude แล้ว update ใน loop เฉย ๆ โดยไม่ max กับ 0 จะพังทันทีเมื่อ gain ติดลบทั้งหมด เพราะจะไม่มีรอบไหนกลับมาแตะ 0 อีกเลย การ initialize 0 ไว้ก่อนจึงการันตีว่าจุดเริ่มต้นถูกนับ

Time O(n) iterate array รอบเดียว · Space O(1) ใช้ตัวแปรสะสมแค่สองตัว ไม่สร้าง array ใหม่

💡 สรุป pattern

เมื่อโจทย์พูดถึง ค่าต่าง/ส่วนเพิ่มทีละก้อน แล้วถามค่าสะสม ให้คิดถึง prefix sum และถ้าต้องการแค่ค่าสุดขั้ว (มากสุด/น้อยสุด) ก็บวกสะสมด้วยตัวแปรเดียวแล้ว track ค่าไป ไม่ต้องเก็บทั้ง array