A peak element is an element that is strictly greater than its neighbors.
Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞.
题意
峰值元素是指其值大于左右相邻值的元素。给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。样例示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
解题
思路一：暴力破解法逐个遍历数组中的元素即可。时间复杂度是O(n)，其中n为数组中的元素个数。空间复杂度是O(1)。
public class Solution {
public int findPeakElement(int[] nums) {
if(1 == nums.length){
return 0;
}
for(int i = 0; i < nums.length; i++){
if(i == 0){
if(nums[0] > nums[1]){
return 0;
}
}else if(i == nums.length - 1){
if(nums[nums.length - 1] > nums[nums.length - 2]){
return nums.length - 1;
}
}else{
if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){
return i;
}
}
}
return -1;
}
}
思路二：二分查找法
思路一显然没有利用题目所给的一个条件——nums[i] ≠ nums[i+1]，且根据题意，我们只需任意找出一个顶峰即可，那么我们可以采取二分查找法。我们取中间mid位置，如果该点满足要求，就直接找到了这个索引，就是mid。否则，我们二分搜索mid索引左边和右边较高的那个点的那一边，我们就一定能找到一个顶峰，这是为什么呢？我们将索引分成2段，[left, mid - 1]，[mid + 1, right]，如果mid不满足要求，那么说明mid - 1和mid + 1这两个位置必然有一个位置的值大于mid位置的值。而mid - 1和mid + 1中的较大者必然是大于mid位置的值的。假设mid - 1位置的值大于等于mid + 1位置的值，那么我们再[left, mid - 1]中一定能找到一个顶峰。因为题目规定了nums[i] ≠ nums[i+1]，而mid - 1位置已经保证了大于mid位置的值，即相当于我们可以把[left, mid - 1]之间的元素看成一个新的数组，其-1和mid位置的值都为-∞，因此在[left, mid - 1]之间比如能找到一个顶峰。。时间复杂度是O(logn)，其中n为数组中的元素个数。空间复杂度是O(1)。public class Solution {
public int findPeakElement(int[] nums) {
return findPeakElement(nums, 0, nums.length - 1);
}
private int findPeakElement(int[] nums, int left, int right){
if(left == right){
return left;
}
int mid = left + (right - left) / 2;
if(mid + 1 < nums.length){
if(mid - 1 >= 0){
if(nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]){
return mid;
}else if(nums[mid + 1] > nums[mid - 1]){
return findPeakElement(nums, mid + 1, right);
}else{
return findPeakElement(nums, left, mid - 1);
}
}else{
if(nums[mid] > nums[mid + 1]){
return mid;
}else{
return findPeakElement(nums, mid + 1, right);
}
}
}else{
if(nums[mid] > nums[mid - 1]){
return mid;
}else{
return findPeakElement(nums, left, mid - 1);
}
}
}
}