题解 | #寻找峰值#

寻找峰值

http://www.nowcoder.com/practice/1af528f68adc4c20bf5d1456eddb080a

寻找峰值

描述

山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。假设 nums[-1] = nums[n] = -∞。

方法一

思路分析

本题相对简单，首先对本题题意进行理解，寻找到的峰值为数组元素中最后的峰值，只需要判断前一个值是否小于当前值就可判断是否为山峰，因此只需要循环遍历一次即可找到最后的峰值。

图解

核心代码

class Solution {
public:
    /**
     * 寻找最后的山峰
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int solve(int* a, int aLen) {
        // write code here
        int index =0;
        int max_element=a[0];
        for(int i=1;i<aLen;i++)
        {
            if(a[i]>a[i-1])
            {
               index=i;//只需要判断前一个值是否小于当前值就可判断是否为山峰
            }
        }
        return index;
    }
};

复杂度分析

时间复杂度：循环遍历一次，所需时间复杂度为$O(n)$
空间复杂度：空间复杂度为$O(1)$

方法二

思路分析

在寻找第二种办法时，我想到了金字塔数组的题目，金字塔数组中先找到所有的波谷，然后寻找波谷间距最大的值，与金字塔数组不同的是，本题需要找所有的波峰，为了便于计算，需要在开始位置与结束位置额外进行比较两个极小值，用于判断开始位置与结束位置是否为波峰。

图解

核心代码

class Solution {
public:
    /**
     * 寻找最后的山峰
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int solve(int* a, int aLen) {
        // write code here
        int index=0;
        for(int i=0;i<aLen;i++)
        {
            if(i==0)//单独判断开始位置是否为山峰
            {
                if(a[i]>INT_MIN&&a[i]>a[i+1])
                    index=i;
            }
            else if(i==aLen-1)//单独判断结束位置是否为山峰
            {
                if(a[i]>INT_MIN&&a[i]>a[i-1])
                    index=i;
            }
            else 
            {
                if(a[i]>a[i-1]&&a[i]>a[i+1])//找到所有的山峰
                index=i;
            }
        }
        return index;//返回最后一个山峰的下标
    }
};

复杂度分析