【Leetcode】162. Find Peak Element

Descrition

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[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 num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution

public int findPeakElement(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return 0;
        }
        if (len == 2) {
            return nums[0] > nums[1] ? 0 : 1;
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        if (nums[len - 1] > nums[len - 2]) {
            return len - 1;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return 0;
    }

Result

AC

Analyse

这个就是简单的数据分析过程。

Optimization

First

public int findPeakElement(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return i - 1;
            }
        }
        return nums.length - 1;
    }

Second

public int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high){
            int mid1 = low + (high - low) / 2;
            int mid2 = mid1 + 1;
            if (nums[mid1] < nums[mid2]) {
                //说明前面还在增加，需要继续向后查，所以low更新
                low = mid2;
            } else {
                high = mid1;
            }
        }
        return low;
    }

Analyse

第一种方法就是利用了本地函数的特性，只要有nums[i] < nums[i - 1]的条件出现就说明有一个peak出现了。第二种方法是二分查找来确定，这个方法不是典型的二分，因为只需要找出其中一个peak就可以了。