1D Peak Finding - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

题目

峰值元素是指其值大于左右相邻值的元素。给你一个输入数组arr，无重复元素，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可，你可以假设 nums[-1] = nums[n] = -∞（两端为-∞）。

详解

寻找峰值 -- 力扣

情况分析

情况 1. 所有的数字以降序排列：第一个元素即为峰值

情况 2. 所有的数字以升序排列：最后一个元素为峰值

情况 3. 峰值出现在中间某处：中间的某个元素为峰值

标准写法（无重复值）

方法一: 线性扫描（时间复杂度：O(n)；空间复杂度：O(1)）

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

方法二: 递归二分查找（时间复杂度：O(logn)；空间复杂度：O(logn)）

public static int findPeakElement(int[] arr) {
    return search(arr, 0, arr.length - 1);
}

public static int search(int[] arr, int low, int high) {
    // 为什么不是low > high?
    // 因为下面不是mid - 1，肯定会出现low == high的情况
    if (low == high) {
        return low;
    }
    int mid = low + (high - low) / 2;
    // 下坡
    if (arr[mid] > arr[mid + 1]) {
        return search(arr, low, mid);
    }
    // 上坡
    else {
        return search(arr, mid + 1, high);
    }
}

方法三: 迭代二分查找（时间复杂度：O(logn)；空间复杂度：O(1)）

public static int findPeakElement(int[] arr) {
    int low = 0, high = arr.length - 1;
    // 写low != high也行
    while (low < high) {
        int mid = (low + high) / 2;
        if (arr[mid] > arr[mid + 1])
            high = mid;
        else
            low = mid + 1;    
    }
    return low;
}

无重复值的二分法时间复杂度分析

T(1) = 1 T(n) = T(n/2) + O(1) T(n) = T(n/2^2) + O(1) + O(1) T(n) = T(n/2^3) + O(1) + O(1) + O(1) ... T(n) = T(n/2^k) + kO(1) 设 n = 2^k 得 k = logn T(n) = T(1) + lognO(1) = O(logn)

若数组arr中有重复元素

此时若arr[mid-1] = arr[mid] = arr[mid+1]，将无法判断应该选左边还是选右边。若选错边，就永远都找不到峰值8。此时二分法就必须两边都要递归

标准写法（有重复值）

public static int findPeakElement(int[] arr) {
    return search(arr, 0, arr.length - 1);
}

public static int search(int[] arr, int low, int high) {
    // 为什么不是low > high?
    // 因为下面不是mid - 1，肯定会出现low == high的情况
    if (low == high) {
        return low;
    }
    int mid = low + (high - low) / 2;
    // 下坡
    if (arr[mid] > arr[mid + 1]) {
        return search(arr, low, mid);
    }
    // 上坡
    else if (arr[mid] < arr[mid + 1]) {
        return search(arr, mid + 1, high);
    }
    // 无法判断左右时，只能两边都递归，找到值较大的一边返回
    else {
        int leftMax = search(arr, low, mid);
        int rightMax = search(arr, mid + 1, high);
        if (arr[leftMax] < arr[rightMax]) {
            return rightMax;
        } else {
            return leftMax;
        }
    }
}

有重复值的二分法时间复杂度分析

T(1) = 1 T(n) = 2T(n/2) + O(1) T(n) = 2^2 * T(n/2^2) + 2O(1) + O(1) T(n) = 2^3 * T(n/2^3) + 4O(1) + 2O(1) + O(1) ... T(n) = 2^k * T(n/2^k) + (2^k - 1)O(1) 设 n = 2^k 得 k = logn T(n) = nT(1) + (n - 1)O(1) = O(2n - 1) = O(n)