941. Valid Mountain Array

📘 題目敘述

給你一個整數陣列 arr，請回傳它是否為合法的 mountain array。

如果一個陣列要是 mountain array，必須同時滿足：

• arr.length >= 3
• 存在某個 i，滿足 0 < i < arr.length - 1，使得：
  • arr[0] < arr[1] < ... < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

也就是說，陣列必須先嚴格遞增，再嚴格遞減，而且山頂不能在最左邊或最右邊。

條件限制

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

🧠 解題思路

這題的重點就是檢查整個陣列有沒有出現一段：

• 先往上爬
• 再往下走

而且這兩段都一定要真的存在，不能只有上坡，也不能只有下坡，更不能中間有平的地方。

我這份寫法用三個東西來記錄目前狀態：

• up：有沒有出現過上升
• down：有沒有出現過下降
• now：前一個數字是什麼

接著一路掃過陣列：

• 如果遇到相等，直接失敗
• 如果目前還在上升，就繼續
• 如果已經開始下降後又再上升，直接失敗
• 最後只有在 up 和 down 都成立時，才是合法 mountain array

所有變數

• up：是否曾經出現過嚴格上升
• down：是否曾經出現過嚴格下降
• now：前一個元素的值

🪜 主要流程步驟

1. 先準備三個狀態變數

bool up = false, down = false;
int now = -1;

這裡：

• up 用來記目前有沒有出現過上升段
• down 用來記目前有沒有出現過下降段
• now 用來記前一個數字

因為題目保證 arr[i] >= 0，所以我先把 now 設成 -1，這樣第一個數字進來時一定會比它大。

2. 一路掃過整個陣列

for (int i : arr) {

這裡直接依序讀每個元素，並和前一個數字 now 比較，判斷目前是在上升、下降，還是出錯。

3. 如果出現相等，直接回傳 false

if (now == i) {
    return false;
}

mountain array 要求的是嚴格遞增、嚴格遞減，所以不能有相等。

只要中間出現：

• ... x, x ...

那就一定不是 mountain array，直接回傳 false。

4. 如果目前是上升，就檢查是不是已經開始下降過

如果現在 i 比前一個數字 now 大，表示目前是在往上爬。

但如果這時候 down 已經是 true，就代表前面明明已經開始下坡了，現在卻又重新上坡，這不符合 mountain array，直接失敗。

如果還沒開始下坡，那這次上升就是合法的，所以把 up 記成 true。 不過第一個元素只是初始化比較，不算真正上升，所以這裡用：

if (now >= 0) {
    up = true;
}

來避免把一開始 -1 -> arr[0] 當成上升段。

5. 如果不是上升也不是相等，那就是下降

else {
    down = true;
}

前面已經排除掉相等，再加上這裡不是上升，所以就只剩下降一種可能。

這表示陣列已經開始下坡了，因此把 down 設成 true。

6. 每次都更新 now

now = i;

目前這個元素處理完之後，就把它記成新的前一個數字，讓下一輪繼續比較。

7. 最後必須同時有上升和下降才算合法

return (up && down) ? true : false;

最後如果：

• up == true
• down == true

代表整個陣列確實有先上升再下降，這才是合法 mountain array。

如果只有其中一個成立，就表示：

• 只有上坡沒有下坡
• 或只有下坡沒有上坡

都不符合題意。

⏱️ 複雜度

設 n = arr.length。

• 時間複雜度：O(n)
  整個陣列只掃一次。
• 空間複雜度：O(1)
  只用了固定數量的變數。

💻 程式碼實作

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        bool up = false, down = false;
        int now = -1;
        for (int i : arr) {
            if (now == i) {
                return false;
            }
            if (now < i) {
                if (down) {
                    return false;
                }
                if (now >= 0) {
                    up = true;
                }
            } else {
                down = true;
            }
            now = i;
        }
        return (up && down) ? true : false;
    }
};

🔗 題目連結

https://leetcode.com/problems/valid-mountain-array/