LeetCode: 941. Valid Mountain Array

問題の要約

• 与えられた配列要素の数値の大小が一つの山を形成するか判定する問題
• 必ず登りから入り、その後必ず下る。水平(同じ数値の連続)は許容しない。

問題

問題へのリンク

回答　その１

• 最初に頂上位置を求め、その左右に勾配があるかを確認

bool validMountainArray(vector<int>& A) {
    int max_i = 0;
    if (A.size()<3) return false;

    for (int i = 0; i<A.size(); i++) 
        if (A[i] > A[max_i]) max_i = i;

    if (max_i == 0 || max_i == (A.size() - 1)) 
        return false;

    for (int i = max_i; i<A.size() - 1; i++) 
        if (A[i] <= A[i + 1]) return false;		

    for (int i = max_i; i>0; i--) 
        if (A[i - 1] >= A[i]) return false;

    return true;
}

時間計算量：O(N)、空間計算量(1)

• 配列長が短すぎないかと頂上位置が先頭または末尾ではないかのチェックを入れた。
• 提出にて Acceptされたが、冗長感あり。Runtime=36 ms、Memory=10.5 MBと普通な結果でした。