ตรวจสอบว่ากลับด้าน subarray หนึ่งทำให้อาร์เรย์เรียงลำดับได้หรือไม่ ใน Python

ปัญหา

ให้อาร์เรย์ nums (ค่าไม่ซ้ำ) ตรวจสอบว่ากลับด้าน subarray เพียง 1 ครั้ง ทำให้อาร์เรย์เรียงได้หรือไม่ (ถ้าเรียงอยู่แล้วก็ True)

ตัวอย่าง

nums = [4,6,27,25,15,9,37,42] → กลับ [9,15,25,27] ได้ [4,6,9,15,25,27,37,42] → True

แนวคิดการแก้ปัญหา

1. หาจุดที่เริ่มไม่เรียง (i)
2. หาจุดที่จบไม่เรียง (j) - ส่วนที่ลดลง
3. ตรวจสอบว่ากลับส่วน [i:j] แล้วเชื่อมกับส่วนก่อนและหลังได้เรียงหรือไม่

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

def solve(nums):
    n = len(nums)
    if n <= 1:
        return True
    
    # หาจุดเริ่มลดลง
    i = 0
    while i < n - 1 and nums[i] < nums[i+1]:
        i += 1
    if i == n - 1:
        return True  # เรียงแล้ว
    
    # หาจุดจบลดลง
    j = i
    while j < n - 1 and nums[j] > nums[j+1]:
        j += 1
    
    # ตรวจสอบเงื่อนไขขอบ
    if i > 0 and nums[j] < nums[i-1]:
        return False
    if j < n - 1 and nums[i] > nums[j+1]:
        return False
    
    # ตรวจสอบส่วนหลัง j เรียงหรือไม่
    for k in range(j, n-1):
        if nums[k] > nums[k+1]:
            return False
    return True

print(solve([4, 6, 27, 25, 15, 9, 37, 42]))  # True

อินพุต / เอาต์พุต

Input:  [4,6,27,25,15,9,37,42]
Output: True