หาความต่างสูงสุดระหว่างตัวเลขน้อยกว่าด้านซ้ายและขวาที่ใกล้ที่สุดใน Python

โจทย์: กำหนดอาร์เรย์ หา |L[i] - R[i]| สูงสุด โดย L[i] = ตัวเลขน้อยกว่า a[i] ใกล้สุดด้านซ้าย (0 ถ้าไม่มี), R[i] = ตัวเลขน้อยกว่า a[i] ใกล้สุดด้านขวา (0 ถ้าไม่มี)

ตัวอย่าง: A=[3,5,9,8,8,10,4] → L=[0,3,5,5,5,8,3], R=[0,4,8,4,4,4,0] → max |L-R| = |8-4| = 4

อัลกอริทึม Monotonic Stack

1. ฟังก์ชัน left_small_element(A, temp): ใช้ stack หา nearest smaller ซ้าย
2. เรียกครั้งแรกกับ A → ได้ left[]
3. เรียกครั้งที่สองกับ A[::-1] (กลับลำดับ) → ได้ right[] (ต้องกลับลำดับกลับมาตอนใช้)
4. วนหา max |left[i] - right[n-1-i]|

ตัวอย่างโค้ด

def left_small_element(A, temp):
    n = len(A)
    stack = []
    for i in range(n):
        while stack and stack[-1] >= A[i]:
            stack.pop()
        temp[i] = stack[-1] if stack else 0
        stack.append(A[i])

def find_maximum_difference(A):
    n = len(A)
    left = [0]*n
    right = [0]*n
    left_small_element(A, left)
    left_small_element(A[::-1], right)
    res = -1
    for i in range(n):
        res = max(res, abs(left[i] - right[n-1-i]))
    return res

A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))  # 4

ผลลัพธ์

4

สรุป: Monotonic Stack หา nearest smaller element ทั้งซ้ายและขวา O(n) time O(n) space เทคนิคกลับอาร์เรย์ใช้ฟังก์ชันเดิมได้