Monotonic Stack — พื้นฐาน & แนวคิด

Monotonic Stack (สแตกที่คงลำดับ) คือการใช้ stack ธรรมดา แต่บังคับให้ element (สมาชิก) ในนั้นเรียงตัวแบบ increasing (เพิ่มขึ้น) เสมอ หรือ decreasing (ลดลง) เสมอ อย่างใดอย่างหนึ่ง เทคนิคนี้ทรงพลังมากกับโจทย์ประเภทหา next greater element (ตัวถัดไปที่มากกว่า) หรือ previous smaller element (ตัวก่อนหน้าที่น้อยกว่า) ซึ่งถ้าทำตรง ๆ ด้วย nested loop (ลูปซ้อน) จะเป็น O(n^2) แต่ monotonic stack ทำได้ใน O(n)

ปัญหาคลาสสิก: Next Greater Element

มี array (ลิสต์) ตัวเลข ถามว่าแต่ละตัวมีตัวไหนอยู่ทางขวาที่มากกว่ามันตัวแรก ถ้าคิดตรง ๆ คือแต่ละตัว iterate (วน) ดูขวาไปเรื่อย ๆ จนเจอตัวที่มากกว่า ซึ่งกรณีแย่สุดเป็น O(n^2) monotonic stack ช่วยให้เรา iterate array รอบเดียวได้

ไอเดียคือเราเก็บ index (ตำแหน่ง) (หรือค่า) ที่ยังหาคำตอบไม่เจอไว้ใน stack โดยรักษาให้ค่าใน stack เรียงจากมากไปน้อยจากล่างขึ้นบน (decreasing) พอเจอตัวใหม่ที่มากกว่ายอด stack ก็แปลว่าตัวใหม่นี่แหละคือ next greater element ของตัวที่ยอด stack เราจึง pop ออกมาแล้วบันทึกคำตอบ

# template: หาตัวถัดไปที่มากกว่า (index) ของแต่ละตำแหน่ง
def next_greater(nums):
    n = len(nums)
    answer = [-1] * n     # ค่าเริ่มต้น -1 = ไม่มีตัวถัดไปที่มากกว่า
    stack = []            # เก็บ index ที่ยังรอตัวมากกว่า (ค่าลดจากล่างขึ้นบน)
    for i in range(n):
        # ถ้าตัวปัจจุบันมากกว่ายอด stack แปลว่าเจอคำตอบของยอดนั้น
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            answer[idx] = i
        stack.append(i)
    return answer

print(next_greater([2, 1, 2, 4, 3]))  # [3, 2, 3, -1, -1]

ทำไมถึงเป็น O(n) ทั้งที่มี while ซ้อนอยู่ กุญแจคือ index แต่ละตัวถูก push (ใส่) เข้า stack แค่ครั้งเดียว และ pop (ดึงออก) แค่ครั้งเดียวตลอดทั้ง loop รวมงานทั้งหมดจึงเป็น O(n) ไม่ใช่ O(n^2) แม้จะเห็น loop ซ้อนกัน