Python - หาความยาวน้อยที่สุดของส่วนแรกที่แยกอาร์เรย์ได้ตามเงื่อนไข

โจทย์: กำหนดรายการตัวเลข nums ต้องการแบ่งเป็น 2 ส่วน part1 และ part2 ที่ ทุกค่าใน part1 ≤ ทุกค่าใน part2 หาความยาวน้อยที่สุดของ part1 (ไม่เป็น 0)

ตัวอย่าง

Input: nums = [3, 1, 2, 5, 4]
Output: 3
เหตุผล: แบ่งได้ part1 = [3, 1, 2], part2 = [5, 4] max(part1)=3 ≤ min(part2)=4

อัลกอริทึม: หาจุดแบ่งจากค่าต่ำสุดและค่าสูงสุดสะสม

ขั้นตอนการทำงาน

1. หา p = min(nums) (ค่าต่ำสุดของทั้งอาร์เรย์)
2. หา s = index แรกที่เจอค่า p
3. อัปเดต p = max(nums[:s+1]) (ค่าสูงสุดในส่วนซ้ายรวม s)
4. ตั้ง ans = s
5. วนจาก s+1 ถึงท้าย: หาก nums[i] < p → ans = i (ต้องขยาย part1)
6. คืนค่า ans + 1

โค้ด Python

def solve(nums):
    p = min(nums)
    s = 0
    
    # หา index แรกของค่าต่ำสุด
    for i in range(len(nums)):
        if nums[i] == p:
            s = i
            break
    
    # ค่าสูงสุดในส่วนซ้าย (รวม s)
    p = max(nums[: s + 1])
    ans = s
    
    # ตรวจสอบส่วนขวา
    for i in range(s + 1, len(nums)):
        if nums[i] < p:
            ans = i
    
    return ans + 1

# ทดสอบ
nums = [3, 1, 2, 5, 4]
print(solve(nums))  # Output: 3

การทำงานทีละขั้นตอน (Trace)

nums = [3, 1, 2, 5, 4]

1. p = min(nums) = 1
2. หา index แรกของ 1 → s = 1
3. p = max(nums[:2]) = max([3, 1]) = 3
4. ans = 1
5. วน i=2: nums[2]=2 < 3 → ans = 2
6. วน i=3: nums[3]=5 ≥ 3 → ไม่เปลี่ยน
7. วน i=4: nums[4]=4 ≥ 3 → ไม่เปลี่ยน
8. คืนค่า ans + 1 = 3

ความซับซ้อน

• Time Complexity: O(n) - ผ่านอาร์เรย์ 2-3 รอบ
• Space Complexity: O(1)

เหตุผลที่ทำงานได้

จุดสำคัญ: ค่าต่ำสุดของทั้งอาร์เรย์ (global min) ต้องอยู่ใน part1 เสมอ (เพราะ part2 ต้อง ≥ ทุกค่าใน part1) ดังนั้นจุดแบ่งต้องอยู่ขวาของ global min อย่างน้อย

การทดสอบเพิ่มเติม

print(solve([1, 2, 3, 4]))      # 1 (part1=[1], part2=[2,3,4])
print(solve([4, 3, 2, 1]))      # 4 (ต้องเอาทั้งอาร์เรย์)
print(solve([2, 1, 3]))         # 2 (part1=[2,1], part2=[3])
print(solve([5, 4, 3, 2, 6]))   # 4 (part1=[5,4,3,2], part2=[6])