寻找峰值

发表于 分类于 阅读次数：

寻找峰值（难度：中等）

1

方法一：线性扫描

利用连续的两个元素 nums[j] 和 nums[j+1] 不会相等这一事实，我们可以从头开始遍历 nums数组，当遇到nums[i] > nums[i+1] ，即可判断 nums[i]为峰值。

注意：不需要判断nums[i]>nums[i-1]。这是由于“遍历会到达第i个元素”本身就说明上一个元素（第i- 1个）不满足 nums[i] > nums[i+1]这一条件，也就说明 nums[i-1] < nums[i]。

复杂度分析

时间复杂度 : O(n)。 只进行一次遍历。 空间复杂度 : O(1)。 只使用了常数空间。

代码
1
2
3
4
5
6
7
8
9
class Solution {
    public int findPeakElement(int[] nums) {
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i+1])
                return i;
        }
        return nums.length-1;
    }
}

方法二：二分法查找

复杂度分析

时间复杂度 : O(logn)。 每一步都将搜索空间减半。 空间复杂度 : O(1)。 只使用了常数空间。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;

        while(left < right){
            int mid = (left+right)/2;
            if(nums[mid]>nums[mid+1]) // 往左搜索
                right = mid;
            else if(nums[mid]<nums[mid+1]) // 往右搜索
                left = mid+1;
        }
        return left;
    }
}
2