题解 | #寻找峰值#
寻找峰值
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;//返回最后一个山峰的下标
}
}; 复杂度分析 - 时间复杂度：循环遍历一次数组，时间复杂度为$O(n)$
- 空间复杂度：空间复杂度为$O(1)$
