Python - หาองค์ประกอบที่แบ่งลำดับเป็น Strictly Decreasing แล้ว Increasing

ได้อาร์เรย์จำนวนบวก ต้องการหาจุดที่ลำดับเปลี่ยนจาก strictly decreasing เป็น strictly increasing ทั้งสองส่วนต้องมีความยาวอย่างน้อย 2 และค่าสุดท้ายของ decreasing = ค่าแรกของ increasing

ตัวอย่าง

Input: [5, 4, 3, 4]

Output: 3 (Decreasing: {5, 4, 3}, Increasing: {3, 4})

อัลกอริธึม

def search_element(arr):
    increase = 1
    decrease = 1
    n = len(arr)
    pt = -1  # pivot point
    
    for i in range(1, n):
        if arr[i] < arr[i-1]:  # Decreasing
            if increase == 1:
                decrease += 1
            else:
                return -1  # เพิ่มแล้วลดอีก → invalid
        
        elif arr[i] > arr[i-1]:  # Increasing
            if increase == 1:
                pt = arr[i-1]  # จุดเปลี่ยน
            if decrease >= 2:
                increase += 1
            else:
                return -1  # ยังไม่ได้ลดพอ
        
        else:  # Equal - not allowed
            return -1
    
    if increase >= 2 and decrease >= 2:
        return pt
    return -1

# ทดสอบ
test_cases = [
    [5, 4, 3, 4],       # 3
    [5, 4, 3, 2, 1],    # -1 (only decreasing)
    [1, 2, 3, 4, 5],    # -1 (only increasing)
    [5, 4, 4, 5],       # -1 (equal not allowed)
    [3, 2, 1, 2, 3],    # 1
    [10, 8, 6, 7, 9],   # 6
]

for arr in test_cases:
    print(f"{arr} -> {search_element(arr)}")

ผลลัพธ์

[5, 4, 3, 4] -> 3
[5, 4, 3, 2, 1] -> -1
[1, 2, 3, 4, 5] -> -1
[5, 4, 4, 5] -> -1
[3, 2, 1, 2, 3] -> 1
[10, 8, 6, 7, 9] -> 6

การวิเคราะห์เงื่อนไข

Alternative: ใช้ Index แทน Value

def find_valley_index(arr):
    """คืน index ของ valley point"""
    n = len(arr)
    if n < 3:
        return -1
    
    # หาจุดที่ arr[i-1] > arr[i] < arr[i+1]
    for i in range(1, n-1):
        if arr[i-1] > arr[i] < arr[i+1]:
            # ตรวจสอบว่า strictly decreasing ก่อนหน้า และ increasing หลัง
            left_ok = all(arr[j] > arr[j+1] for j in range(i))
            right_ok = all(arr[j] < arr[j+1] for j in range(i, n-1))
            if left_ok and right_ok:
                return i
    return -1

ความซับซ้อน

• Time: O(n) - single pass
• Space: O(1) - constant extra space

สรุป

• หาจุด "Valley" (หุบเขา) ในลำดับ
• ต้องมี decreasing ≥ 2 elements และ increasing ≥ 2 elements
• Strictly = ไม่มีค่าเท่ากันติดกัน
• คืนค่าที่จุดเปลี่ยนทิศทาง (pivot value)