C语言重构【852】山脉数组的峰顶索引

Myth丶恋晨 2022-12-20 02:06 154阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

我们把符合下列属性的数组 A 称作山脉：
    
    A.length >= 3
    存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
    给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。
    
     
    
    示例 1：
    
    输入：[0,1,0]
    输出：1
    示例 2：
    
    输入：[0,2,1,0]
    输出：1
     
    
    提示：
    
    3 <= A.length <= 10000
    0 <= A[i] <= 10^6
    A 是如上定义的山脉

#### 方案： ####

class Solution
    { 
    public:
        int peakIndexInMountainArray(vector<int> &arr)
        { 
            //i有的话必定只有一个，没有就没有
            int len = arr.size();
            int peak = -1;
            for (int i = 1; i < len; i++)
            { 
                if (peak == -1)
                { 
                    if (arr[i] < arr[i - 1])
                        peak = i - 1;
                }
                else
                { 
                    if (arr[i] > arr[i - 1])
                        return -1;
                }
            }
            return peak;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode