【LeetCode】162. Find Peak Element 寻找峰值（Medium）（JAVA）
题目地址: https://leetcode.com/problems/find-peak-element/
题目描述：
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
Follow up: Your solution should be in logarithmic complexity.
题目大意
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
解题方法
- 题目里规定了采用 log(n) 的时间复杂度，如果采用 O(n) 的时间复杂度，直接遍历即可
- 分为两部分，通过 nums[mid] > num[mid + 1] 可以知道 一定在前半部分，否则在后半部分
- 因为没有峰值的前部分肯定是单调递增的，没有峰值的后半部分是单调递减的
class Solution {
public int findPeakElement(int[] nums) {
if (nums.length <= 1) return 0;
return findPeakElement(nums, 0, nums.length - 1);
}
public int findPeakElement(int[] nums, int start, int end) {
if (start > end) return -1;
if (start == end) return start;
int mid = start + (end - start) / 2;
if (nums[mid] > nums[mid + 1]) return findPeakElement(nums, start, mid);
return findPeakElement(nums, mid + 1, end);
}
}
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38.1 MB,击败了81.76% 的Java用户