LeetCode 解題練習：Valid Mountain Array

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/valid-mountain-array/

中文描述

給定一個整數陣列 arr，檢查此陣列是否為一個合格的山脈陣列(Valid Mountain Array)。Valid Mountain Array 的定義如下：

• 陣列長度大於等於3。
• 存在一個整數 i ，且 0 < i < 陣列長度，使得底下條件成立：
• arr[0] < arr[1] < arr[2] < ... < arr[i-2] < arr[i-1] < arr[i]
• arr[arr.length - 1] < arr[arr.length - 2] < arr[arr.length - 3] < .... < arr[i + 2] < arr[i + 1] < arr[i]

 

範例一：

輸入 arr = [1, 2]

輸出 false

因為陣列長度小於 3

範例二：

輸入 arr = [1, 2, 1]

輸出 true

範例三：

輸入 arr = [1, 2, 2, 3, 1]

輸出 false

因為 arr[1] = 2 = arr[2]，非嚴格遞增。 

範例四：

輸入 arr = [1, 2, 3, 3, 2, 1]

輸出 false

因為 arr[2] = 3 = arr[3]，非嚴格遞減。 

解法一：

left 從左邊開始往右找，找到非嚴格遞增的位置。

right = left + 1，繼續往右找，找到非嚴格遞減的位置。

回傳 left != 0 and left < len(arr) - 1 and right == len(arr)。

Python Code 

class Solution:

    def validMountainArray(self, arr: List[int]) -> bool:

        left = 0

        while left < len(arr) - 1:

            if arr[left] >= arr[left + 1]: # 若找到非嚴格遞增

                break

            left += 1

        right = left + 1

        while right < len(arr):

            if arr[right - 1] <= arr[right]: # 若找到非嚴格遞減

                break

            right += 1

       

        return left != 0 and left < len(arr) - 1 and right == len(arr)

       

解法二：

left 從左邊開始往右找，找到非嚴格遞增的位置。

right 從右邊開始往左找，找到非嚴格遞減的位置。

回傳 left != 0 and left == right and right != len(arr) - 1

Python Code

class Solution:

    def validMountainArray(self, arr: List[int]) -> bool:

        left = 0

        while left < len(arr) - 1:

            if arr[left] >= arr[left + 1]: # 若找到非嚴格遞增

                break

            left += 1

        right = len(arr) - 1

        while right > 0:

            if arr[right - 1] <= arr[right]: # 若找到非嚴格遞減

                break

            right -= 1

       

        return left != 0 and left == right and right != len(arr) - 1