LeetCode 155: Min Stack เก็บค่าต่ำสุดอย่างไรให้ทุกคำสั่ง O(1)

โจทย์ Min Stack ให้สร้าง stack ที่รองรับ push, pop, top และ getMin โดยทุกคำสั่งต้องเวลา O(1) ครับ Stack ปกติรู้เฉพาะของบนสุด ถ้าของต่ำสุดอยู่กลางกองแล้วถูกดันของใหม่ทับ เราต้องจำประวัติให้พอกลับมาได้หลัง pop

WHY: ค่าต่ำสุดเป็น State ตามระดับความลึก

การเก็บ current minimum ตัวเดียวพอจนกว่าค่านั้นถูก pop หลังจากนั้นเราไม่รู้ค่าต่ำสุดก่อนหน้า เหมือนจดสถิติต่ำสุดของวันไว้ใบเดียวแล้วฉีกทิ้งโดยไม่มีสมุดย้อนหลัง วิธี O(1) จึงต้องเก็บข้อมูล minimum ตามจังหวะ push

วิธี 1: สแกนตอน getMin

เก็บ stack เดียว push/pop/top O(1), getMin O(n), พื้นที่ O(n) implementation ง่ายแต่ไม่ผ่าน constraints เหมาะเฉพาะระบบจริงที่แทบไม่ถาม min และยอมแลก latency ได้

วิธี 2: Dual Stack

stack แรกเก็บค่าจริง stack ที่สองเก็บ minimum เมื่อค่าที่ push น้อยกว่าหรือเท่าค่าบนสุด เวลา O(1) ทุกคำสั่ง พื้นที่เพิ่มสูงสุด O(n) เข้าใจง่าย แต่ต้องระวังค่า min ซ้ำ: ใช้ <= ตอน push และ pop ทั้งสองเมื่อเท่ากัน

วิธี 3: Pair Stack

ทุกชั้นเก็บคู่ (value, minimum_so_far) เวลา O(1), พื้นที่ O(n) ที่มี overhead คงที่ต่อ item ไม่มี synchronization ระหว่างสอง stack จึงเป็น best default ด้าน readability

วิธี 4: Encoded Difference

เก็บส่วนต่าง value - current_min และ update min ตามเครื่องหมาย ใช้หนึ่ง stack กับตัวแปร min เวลา O(1), พื้นที่ O(n) ลดโครงสร้างคู่ แต่เหตุผลซับซ้อนและภาษา fixed-width อาจ overflow เหมาะเมื่อวัดแล้ว memory overhead เป็นคอขวดจริง

import unittest


class PairMinStack:
    def __init__(self):
        self.items = []

    def push(self, value):
        minimum = value if not self.items else min(value, self.items[-1][1])
        self.items.append((value, minimum))

    def pop(self):
        return self.items.pop()[0]

    def top(self):
        return self.items[-1][0]

    def get_min(self):
        return self.items[-1][1]


class DualMinStack:
    def __init__(self):
        self.values = []
        self.minimums = []

    def push(self, value):
        self.values.append(value)
        if not self.minimums or value <= self.minimums[-1]:
            self.minimums.append(value)

    def pop(self):
        value = self.values.pop()
        if value == self.minimums[-1]:
            self.minimums.pop()
        return value

    def top(self):
        return self.values[-1]

    def get_min(self):
        return self.minimums[-1]


class EncodedMinStack:
    def __init__(self):
        self.differences = []
        self.minimum = None

    def push(self, value):
        if not self.differences:
            self.differences.append(0)
            self.minimum = value
            return
        difference = value - self.minimum
        self.differences.append(difference)
        if difference < 0:
            self.minimum = value

    def pop(self):
        difference = self.differences.pop()
        value = self.minimum if difference < 0 else self.minimum + difference
        if difference < 0:
            self.minimum = self.minimum - difference
        if not self.differences:
            self.minimum = None
        return value

    def top(self):
        difference = self.differences[-1]
        return self.minimum if difference < 0 else self.minimum + difference

    def get_min(self):
        return self.minimum


class MinStackTests(unittest.TestCase):
    def test_implementations_with_duplicate_minimum(self):
        for stack_type in (PairMinStack, DualMinStack, EncodedMinStack):
            stack = stack_type()
            for value in (3, -2, -2, 5):
                stack.push(value)
            self.assertEqual(stack.get_min(), -2)
            self.assertEqual(stack.pop(), 5)
            self.assertEqual(stack.pop(), -2)
            self.assertEqual(stack.get_min(), -2)
            self.assertEqual(stack.top(), -2)
            self.assertEqual(stack.pop(), -2)
            self.assertEqual(stack.get_min(), 3)


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

Decision Table

เงื่อนไข	Scan on min	Dual stack	Pair stack	Encoded diff
input ใหญ่และ getMin บ่อย	ไม่ผ่าน O(n)	ดี	ดีที่สุด	ดี
memory จำกัด	ข้อมูลน้อยสุด	min ซ้ำเพิ่ม	คู่ทุกชั้น	โครงสร้างเดียว
readability	ง่ายแต่ผิด constraint	ชัด	ชัดที่สุด	ยาก
streaming operations	ได้	ได้	ได้	ได้
sorted input	ไม่ช่วยข้อกำหนดทั่วไป	ไม่ต้องพึ่ง	ไม่ต้องพึ่ง	ไม่ต้องพึ่ง
แก้ input เดิม	ไม่มี input collection	ไม่มี	ไม่มี	ไม่มี
ภาษา integer overflow ได้	ปลอดภัยกว่า	ปลอดภัยกว่า	ปลอดภัยกว่า	ต้องระวังมาก

Edge Cases และ Best Default

ค่า minimum ซ้ำ, เลขติดลบ, push หลัง stack ว่าง และการ pop จนว่างต้องทดสอบ โจทย์รับประกันว่าจะไม่เรียก top/getMin ตอนว่าง แต่ production API ควรกำหนด exception หรือ Optional ชัดเจน

pair stack เป็น best default เพราะ invariant อยู่ใน item เดียว: ชั้นใดอยู่บนสุด minimum ของชั้นนั้นคือคำตอบ Dual stack ประหยัดกว่าเมื่อ minimum เปลี่ยนน้อย ส่วน encoded difference ควรใช้หลัง profile เท่านั้น

Recap

• current minimum เดี่ยวกู้ค่าก่อนหน้าไม่ได้
• dual stack ต้องจัดการ minimum ซ้ำ
• pair stack ชัดและ O(1) ทุกคำสั่ง
• encoded difference เสี่ยง overflow ในภาษาบางชนิด
• เลือก pair stack เป็นค่าเริ่มต้นเพื่อความอ่านง่าย