LeetCode 941: Valid Mountain Array

問題描述

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

限制條件

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

範例

• Example 1:
  Input: arr = [2, 1]
Output: false
• Example 2:
  Input: arr = [3, 5, 5]
Output: false
• Example: 3
  Input: arr = [0, 3, 2, 1]
Output: true

解法一：一次迭代

步驟詳解

1. 基本情況 (Base Case)：根據 mountain array 的定義，若 arr 長度小於 3 或是 arr 從一開始就是處於下坡的狀態 (arr[0] > arr[1])，我們可以在這裡就直接回傳 False.
2. 使用一個變數 peak_reached 來紀錄我們是否已經抵達過峰頂 (peak)。
3. 遍歷 arr：
   1. 若當前元素 arr[i] 與下一個元素 arr[i + 1] 相同，根據定義，此為無效 mountain array，這邊直接回傳 False.
   2. 若當前元素 arr[i] 比下一個的元素 arr[i + 1] 大，代表我們已經抵達峰頂，而接下來的元素都只能是遞減排列。將 peak_reached 設為 True。
   3. 否則的話，若我們已經抵達過峰頂但當前元素 arr[i] 卻比下一個元素 arr[i + 1] 小，代表我們又重新爬坡了一次，根據定義也是無效的 mountain array，直接回傳 False。
4. 遍歷結束後為回傳 peak_reached 確保我們曾經有抵達過峰頂，因為單調上升 (monotone increasing) 並非有效的 mountain array。

程式碼

def valid_mountain_array(arr: List[int]) -> bool:
    if len(arr) < 3 or arr[0] > arr[1]:
        return False

    peak_reached = False
    for i in range(len(arr) - 1):
        if arr[i] == arr[i + 1]:
            return False
        elif arr[i] > arr[i + 1]:
            peak_reached = True
        else:
            if peak_reached:
                return False

    return peak_reached

複雜度分析

• 時間複雜度：O(N)，其中 N 為 arr 的陣列長度。
• 空間複雜度：O(1)

參考資料

• LeetCode 原題出處：Valid Mountain Array – LeetCode