941. 有效的山脈數組

思路

先從左邊往右判斷遞增最後結束的地方（閉區間），紀錄為left
再從右邊往左判斷遞減最後結束的地方（閉區間），紀錄為right
如果left == right，表示有山峰。

需要注意當left == 0或right == n - 1時，
表示整個數組是只有嚴格遞增或嚴格遞減其中一種，不算作山峰存在

程式碼

雙指針

class Solution {
public:
    bool validMountainArray(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) return false;
        int left = 0, right = n - 1;
        while(left + 1 < n && nums[left] < nums[left + 1]) {
            ++left;
        }
        while(right - 1 >= 0 && nums[right - 1] > nums[right]) {
            --right;
        }
        return left == right && left != 0 && right != n - 1;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$