数组中等 NC107 寻找峰值 LeetCode162. 寻找峰值

162. 寻找峰值

描述

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

分析

参考：https://leetcode-cn.com/problems/find-peak-element/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-qva7v/
可以使用暴力遍历数组找到峰值，但是二分法更快。
可以使用二分法的原因：
1.数组一定存在峰值
2.通过二分法可以找到峰值

二分法解法：

class Solution {public int findPeakElement(int[] nums) {if(nums.length == 1){return 0;}int left = 0, right = nums.length-1;while(left != right){int mid = (right - left) / 2 + left;if(nums[mid] > nums[mid-1]){left = mid;}else{right = mid-1;}}return left;}
}

暴力解法

import java.util.*;
public class Solution {public int findPeakElement (int[] nums) {int n = nums.length;if(n == 1 || nums[0] > nums[1]){return 0;}if(nums[n-1] > nums[n-2]){return n-1;}for(int i = 1; i < n-1; i++){if(nums[i] > nums[i-1] && nums[i] > nums[i+1]){return i;}}return 1;}
}