Day77 寻找峰值

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可

https://leetcode-cn.com/problems/find-peak-element/

峰值元素是指其值大于左右相邻值的元素。

你可以假设 nums[-1] = nums[n] = -∞ 。 进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？

示例1：

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

示例2：

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

提示：

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

Java解法

思路：

• 先进行普通解吧，左右元素比自身小即可的话，按此遍历即可
• 进阶解：时间上O(logN)的需求很容易想到归并，二分查找，在这里可以尝试用二分查找来做
  • 参考官方解：我思考的有点复杂了，找到中点计算，实际上是用二分查找来排除不需要计算的部分

package sj.shimmer.algorithm.m4_2021;

/**
 * Created by SJ on 2021/4/14.
 */

class D77 {
    public static void main(String[] args) {
        System.out.println(findPeakElement2(new int[]{1, 2, 3, 1}));
        System.out.println(findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4}));
    }

    public static int findPeakElement(int[] nums) {
        int pre = Integer.MIN_VALUE;
        int next = Integer.MIN_VALUE;
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {
            next = nums[i + 1];
            if (nums[i] > pre && nums[i] > next) {
                return i;
            }
            pre = nums[i];
        }
        if (next > pre && next > Integer.MIN_VALUE) {
            return length - 1;
        }
        return 0;
    }

    public static int findPeakElement2(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}

image

image

官方解

https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode/

1. 线性扫描

   如上

   • 时间复杂度：O(n)

• 空间复杂度：O(1)

2. 递归二分查找及迭代二分查找

   • 时间复杂度：O(log2(n))
   • 空间复杂度：O(1)