Mảng núi hợp lệ (Valid Mountain Array) trong Python

Giả sử ta có mảng A số nguyên; kiểm tra xem có phải mảng núi hợp lệ không. Biết A là mảng núi nếu và chỉ nếu thỏa: độ dài A >= 3

Tồn tại chỉ số i sao cho:

• A[0] < A[1] < ... A[i-1] < A[i]
• A[i] > A[i+1] > ... > A[A.length - 1]

Ví dụ, đầu vào [0,3,2,1], đầu ra True.

Giải quyết:

• if len(A) < 3, return False
• i := 1
• while i < len(A) and A[i] > A[i-1], i += 1
• 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)

Xem triển khai:

Ví dụ

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
        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]))

Đầu vào

[0,3,2,1]

Đầu ra

True