LeetCode 162. Find Peak Element

Problem

LeetCode 162. Find Peak Element

1. 题目简述

给出一个数组，找到其中一个peak element的index。peak element指的是严格大于其相邻两个数的元素。保证相邻的两个数字不相同，且假设 nums[-1] = nums[n] = -∞。

Example: 
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Constraints:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.

2. 算法思路

Binary Search

y总解析传送门，想法真的很巧妙：链接

当我们比较a[i]和a[i + 1]时，如果a[i] < a[i + 1]，那么假设a[i…n]是单调递增的，那么a[n]就是一个peak；如果a[i…n]不是单调递增的，那么一定存在一个拐点下降，拐点下降的地方就是peak。其中一定存在peak，因为nums[-1] = nums[n] = -∞。如果a[i] > a[i + 1]，同理，a[1…i + 1]一定存在一个拐点。那么对于等于的情况呢？题中保证了nums[i] != nums[i + 1]。

3. 解法

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        
        int l = 0, r = nums.length - 1;
        
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[mid + 1]) {
                // 这里仔细想想，mid可能是峰值么？不可能的，因为nums[mid] < nums[mid + 1]，因此l = mid + 1。
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        
        return r;
    }
}