Leaky Cauldron
0%

寻找峰值

Posted on Edited on

寻找峰值元素 (LeetCode #162)

给定一个输入数组 nums ，其中 nums[i] ≠ nums[i+1] ，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

说明:

解法应该是 O(logN) 时间复杂度的.

题解

本题采用二分法, 假定最后一个元素的索引为 N, 首先判断 0 和 1 位置元素, N 和 N-1 位置元素的大小关系, 若 num[0] > num[1] 或 num[N] > num[N-1] , 则返回 0 或 N 即可. 若前两个条件均不满足则 0 和 N 之间必有峰值, 取中间元素 num[mid] , 若该元素也不是峰值, 则继续二分. 若 num[mid] < num[mid-1] , 则峰值必在 0 和 mid 之间, 反之则在 mid 与 N 之间.

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

        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) right = mid;	// 左边高, 峰值在左, 可能是 mid
            else left = mid + 1; // 右边高, 峰值在右, 包含 mid + 1
        }

        return left;
    }
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
class FindPeakElement:
    def findPeakElement(self, nums):
        left = 0
        right = len(nums) - 1
        mid = 0

        while (left < right):
            mid = left + (right - left) // 2
            if nums[mid] > nums[mid + 1]: right = mid
        	else: left = mid + 1

        return left