162.寻找峰值

【LetMeFly】162.寻找峰值：二分查找

力扣题目链接：https://leetcode.cn/problems/find-peak-element/

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

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

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

你必须实现时间复杂度为 O(log 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。

 

提示：

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

方法一：遍历

直接无脑遍历即可。

方法二：二分查找

根据题目条件不难看出：相邻两个元素不等（数据范围课看出）、数组越界处的值相当于无限小。因此答案一定存在：加上数组外侧两元素，从最左到最右，元素先增后减（不可能一直增），第一个“增后减”的元素即为第一个“波峰”。

这怎么用二分解决呢？用二分查找的思路，对于元素$nums[mid]$：

• 若左右相邻元素都小于它，则直接返回

• 若左边元素小于它，则这个元素右边一定存在“波峰”（将[mid + 1, len(nums)]看成新的数组）

• 若右边元素小于它，则这个元素左边一定存在“波峰”（将[-1, mid - 1]看成新的数组）

• 若左右相邻元素都大于它，则左右都一定存在“波峰”（可以和第三条一同考虑）

• 时间复杂度$O(\log len(nums))$

• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if ((mid - 1 < 0 || nums[mid - 1] < nums[mid]) && (mid + 1 == nums.size() || nums[mid + 1] < nums[mid])) {
                return mid;
            }
            if (mid - 1 < 0 || nums[mid - 1] < nums[mid]) {  // 左边小 说明右边大
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        return -1;  // FakeReturn
    }
};

Python

# from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) >> 1
            if (mid - 1 < 0 or nums[mid - 1] < nums[mid]) and (mid + 1 == len(nums) or nums[mid + 1] < nums[mid]):
                return mid
            if mid - 1 < 0 or nums[mid - 1] < nums[mid]:
                l = mid + 1
            else:
                r = mid
        return -1

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135067872