LeetCode #121 Best Time to Buy and Sell Stock: จำราคาต่ำสุดครั้งเดียว

โจทย์ best-time-to-buy-and-sell-stock ให้ราคาหุ้นรายวัน เราซื้อได้หนึ่งครั้งแล้วขายภายหลังหนึ่งครั้ง ต้องหากำไรสูงสุด ถ้าไม่มีทางกำไรให้ตอบศูนย์ คำว่า “ขายภายหลัง” สำคัญ: เราห้ามเลือกจุดสูงก่อนจุดต่ำ

วิธีที่ 1: ลองทุกคู่

เลือกวันซื้อ i แล้วลองวันขาย j > i ทุกวัน เก็บส่วนต่างสูงสุด เวลา O(n²), พื้นที่ O(1) ข้อดีคืออธิบายตรงโจทย์และใช้เป็น oracle ทดสอบวิธีเร็วบน input เล็ก ข้อเสียคือช้าเมื่อข้อมูลยาว

วิธีที่ 2: suffix maximum

สร้างอาร์เรย์ที่แต่ละตำแหน่งเก็บราคาสูงสุดทางขวา แล้วคำนวณกำไรสำหรับทุกวันซื้อ เวลา O(n), พื้นที่ O(n) เหมาะเมื่อ suffix maximum ถูกใช้กับคำถามอื่นด้วย แต่ถ้าต้องการแค่กำไรตัวเดียว พื้นที่เกินจำเป็น

วิธีที่ 3: one-pass minimum (แนะนำหลัก)

เดินซ้ายไปขวา เก็บราคาต่ำสุดที่เคยเห็นและกำไรสูงสุดจากการขายวันนี้ เวลา O(n), พื้นที่ O(1) ลำดับอัปเดตควรคำนวณกำไรก่อนหรือหลัง minimum ก็ได้เมื่อยอมซื้อขายวันเดียวกำไรศูนย์ แต่ต้องรักษาความหมายว่าราคาซื้อมาจากอดีตหรือปัจจุบัน

วิธีที่ 4: state machine / DP

เก็บ state “ถือหุ้น” และ “ไม่ถือหุ้นหลังขาย” ทำได้ O(n)/O(1) เช่นกัน มีประโยชน์เมื่อจะต่อยอดไปหลายธุรกรรม ค่าธรรมเนียม หรือ cooldown แต่สำหรับข้อ 121 มักซับซ้อนเกินโจทย์

import unittest


def max_profit(prices):
    lowest = float("inf")
    best = 0
    for price in prices:
        best = max(best, price - lowest)
        lowest = min(lowest, price)
    return best


def max_profit_bruteforce(prices):
    return max(
        0,
        max(
            (prices[j] - prices[i] for i in range(len(prices))
             for j in range(i + 1, len(prices))),
            default=0,
        ),
    )


class StockTests(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [
            ([7, 1, 5, 3, 6, 4], 5),
            ([7, 6, 4, 3, 1], 0),
            ([2], 0),
            ([2, 2, 2], 0),
        ]
        for prices, expected in cases:
            with self.subTest(prices=prices):
                self.assertEqual(max_profit(prices), expected)
                self.assertEqual(max_profit(prices), max_profit_bruteforce(prices))


if __name__ == "__main__":
    unittest.main()

เลือกวิธีไหนดี

สถานการณ์	วิธี	เหตุผล
เรียนอัลกอริทึมครั้งแรก	ทุกคู่	เห็นข้อจำกัดลำดับวันชัด
สัมภาษณ์ข้อ 121	one-pass minimum	O(n), O(1), พิสูจน์ง่าย
ต้องใช้ข้อมูลอนาคตหลายคำถาม	suffix maximum	reuse อาร์เรย์ได้
กำลังต่อยอดกติกาซื้อขาย	state machine	เพิ่ม state ได้เป็นระบบ

เคสที่ต้องพูดให้ครบคือราคาลดตลอด, ราคาเท่ากัน, อาร์เรย์สั้น และค่าต่ำสุดเกิดหลังจุดสูงสุด วิธี one-pass ถูกเพราะประเมินกำไรตามลำดับเวลาเสมอ

Recap

คำตอบ default คือเก็บ minimum-so-far และ best-profit ในรอบเดียว อธิบาย invariant ว่า minimum มาจาก prefix ที่เห็นแล้ว และใช้ brute force เป็น test oracle บนข้อมูลสุ่มขนาดเล็กได้ครับ