题目描述

这是 LeetCode 上的「162. 寻找峰值」，难度为「中等」。

Tag : 「二分」

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

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

你可以假设 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\le num.length \le 1000\)
• \(-2^{31}\le nums[i] \le 2^{31}-1\)
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

模拟

由于数据范围只有 1000，使用线性扫描找峰值的模拟做法也是没有问题。

代码：

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean ok = true;
            if (i - 1 >= 0) {
                if (nums[i - 1] >= nums[i]) ok = false;
            }
            if (i + 1 < n) {
                if (nums[i + 1] >= nums[i]) ok = false;
            }
            if (ok) return i;
        }
        return -1;
    }
}

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

二分

题目让我们实现一个\(O(logn)\)  算法，这是对使用「二分」的强烈暗示。

和往常的题目一样，我们应当从是否具有「二段性」来考虑是否可以进行「二分」。

不难发现，如果 在确保有解的情况下，我们可以根据当前的分割点 mid 与左右元素的大小关系来指导l 或者r 的移动。

假设当前分割点mid 满足关系num[mid]> num[mid+1] 的话，一个很简单的想法是 num[mid]可能为峰值，而num[mid+1] 必然不为峰值，于是让r = mid ，从左半部分继续找峰值。

估计不少同学靠这个思路 AC 了，只能说做法对了，分析没对。

上述做法正确的前提有两个：

1. 对于任意数组而言，一定存在峰值（一定有解）；
2. 二分不会错过峰值。

我们分别证明一下。

证明 1 ：对于任意数组而言，一定存在峰值（一定有解）

根据题意，我们有「数据长度至少为 1」、「越过数组两边看做负无穷」和「相邻元素不相等」的起始条件。

我们可以根据数组长度是否为 进行分情况讨论：

1. 数组长度为 1，由于边界看做负无穷，此时峰值为该唯一元素的下标；
2. 数组长度大于1 ，从最左边的元素num[0] 开始出发考虑：
   • 如果在到达数组最右侧前，出现num[i]>nums[i+1] ，说明存在峰值位置 i（当我们考虑到 num[i]，必然满足 num[i] 大于前一元素的前提条件，当然前一元素可能是原始左边界）；
   • 到达数组最右侧，还没出现num[i]>nums[i+1] ，说明数组严格递增。此时结合右边界可以看做负无穷，可判定 nums[n-1]为峰值。
   • 如果num[0]>num[1] ，那么最左边元素num[0] 就是峰值（结合左边界为负无穷）；
   • 如果 num[0]<num[1] ，由于已经存在明确的num[0]   和 num[1]大小关系，我们将num[0]  看做边界，num[1]看做新的最左侧元素，继续往右进行分析：

综上，我们证明了无论何种情况，数组必然存在峰值。

证明 2：二分不会错过峰值

其实基于「证明 1」，我们很容易就可以推理出「证明 2」的正确性。

整理一下由「证明 1」得出的推理：如果当前位置大于其左边界或者右边界，那么在当前位置的右边或左边必然存在峰值。

换句话说，对于一个满足nums[x]>nums[x-1]的位置，x的右边一定存在峰值；或对于一个满足nums[x]>nums[x+1]的位置，x的左边一定存在峰值。

因此这里的「二段性」其实是指：在以mid为分割点的数组上，根据nums[mid]与\(nums[mid \pm 1]\)的大小关系，可以确定其中一段满足「必然有解」，另外一段不满足「必然有解」（可能有解，可能无解）。

如果不理解为什么「证明2 」的正确性可以由「证明1 」推导而出的话，可以重点看看「证明1 」的第2点的证明。

至此，我们证明了始终选择大于边界一端进行二分，可以确保选择的区间一定存在峰值，并随着二分过程不断逼近峰值位置。

另外，为了照顾还在纠结使用什么“模板”的同学，特意写了两个版本。但其实只要搞清楚我们「二分」什么内容，根本不会存在说用哪种方式才能写过的情况。

代码：

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > nums[mid - 1]) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}

• 时间复杂度：\(O(logn)\)
• 空间复杂度：\(O(1)\)

总结

通过本题，我们可以对「二分」有进一步的认识。

最早在 33. 搜索旋转排序数组 中，我们强调，二分的本质是「二段性」而非「单调性」，而经过本题，我们进一步发现「二段性」还能继续细分，不仅仅只有满足01特性（满足/不满足）的「二段性」可以使用二分，****满足1?特性（一定满足/不一定满足）也可以二分****。