0162. 寻找峰值 Find Peak Element

问题描述

这个题目中的数组并不是有序的, 所以可以先考虑暴力法.

Brute force

遍历整个数组, 找到比左侧和右侧都大的那个元素.

但首先要检查边界情况, 即第一个元素和最后一个元素.

#![allow(unused)]
fn main() {
// Brute Force
// O(n)
pub fn find_peak_element1(nums: Vec<i32>) -> i32 {
    debug_assert!(!nums.is_empty());
    if nums.len() == 1 {
        return 0;
    }
    // 先处理边界情况.
    if nums[0] > nums[1] {
        return 0;
    }
    let last = nums.len() - 1;
    if nums[last - 1] < nums[last] {
        return last as i32;
    }

    // 检查剩下的元素.
    for i in 1..last {
        if nums[i - 1] < nums[i] && nums[i] > nums[i + 1] {
            return i as i32;
        }
    }

    -1
}
}

该算法的时间复杂度是 O(n).

二分查找法

这个表面上看, 并不能直接使用二分查找法. 但是, 这个题目只要求找到极大值, 并没有要求找到数组中的最大值, 所以仍然可以用二分查找法找出 比左侧和右侧都大的元素.

二分法中的 middle 元素与可能的极大值的关系有三种:

• middle 处就是峰值
• middle 位于峰值的左侧
• middle 位于峰值的右侧

我们编写二分查找法时, 就可以根据这些情况来处理:

#![allow(unused)]
fn main() {
// Binary Search
pub fn find_peak_element2(nums: Vec<i32>) -> i32 {
    debug_assert!(!nums.is_empty());

    if nums.len() == 1 {
        return 0;
    }

    // 先处理边界情况.
    // 这里先检查第一个和最后一个元素.
    if nums[0] > nums[1] {
        return 0;
    }
    let last = nums.len() - 1;
    if nums[last - 1] < nums[last] {
        return last as i32;
    }

    // 使用二分法找一个峰值, 检查数组中剩下的元素.
    let mut left = 1;
    let mut right = last - 1;
    while left <= right {
        // 峰值出现的位置与 nums[middle] 的关系有三种情况.
        let middle = left + (right - left) / 2;
        if nums[middle] > nums[middle + 1] && middle > 0 && nums[middle] > nums[middle - 1] {
            // 1. middle 处就是峰值
            return middle as i32;
        }
        if nums[middle] < nums[middle + 1] {
            // 2. 峰值在 middle 的右侧
            left = middle + 1;
        } else if middle > 0 && nums[middle] < nums[middle - 1] {
            // 3. 峰值在 middle 的左侧
            right = middle - 1;
        }
    }

    -1
}
}

该算法的时间复杂度是 O(log(n)).