Valid Mountain Array (ตรวจสอบ Array รูปภูเขา) ใน Python

โจทย์: ตรวจสอบว่า Array เป็น "Mountain Array" หรือไม่ คือ เพิ่มขึ้นอย่างเคร่งครัด (Strictly increasing) แล้วตามด้วยลดลงอย่างเคร่งครัด (Strictly decreasing)

เงื่อนไข Mountain Array

• ความยาว ≥ 3
• มี Peak (ยอดเขา) อยู่ที่ Index i (0 < i < n-1)
• A[0] < A[1] < ... < A[i] > A[i+1] > ... > A[n-1]

Input/Output

Input:  [0, 3, 2, 1]
Output: True

อัลกอริทึม: Two Pass

1. เช็คความยาว < 3 → False
2. เดินขึ้นหา Peak: while i < n และ A[i] > A[i-1]: i++
3. เช็ค Peak: i == 0 (ไม่ได้ขึ้น) หรือ i == n (ไม่ได้ลง) → False
4. เดินลง: while i < n และ A[i] < A[i-1]: i++
5. ถ้า i == n → True (เดินครบทุกตัว)

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

class Solution:
    def validMountainArray(self, A):
        if len(A) < 3:
            return False
        
        i = 1
        # เดินขึ้น
        while i < len(A) and A[i] > A[i-1]:
            i += 1
        
        # เช็ค Peak
        if i == 1 or i == len(A):
            return False
        
        # เดินลง
        while i < len(A) and A[i] < A[i-1]:
            i += 1
        
        return i == len(A)

ob = Solution()
print(ob.validMountainArray([0, 3, 2, 1]))

ผลลัพธ์

True

Edge Cases: [1,2,3] (ขึ้นอย่างเดียว) → False, [3,2,1] (ลงอย่างเดียว) → False, [1,2,2,1] (มีค่าเท่ากัน) → False