Leetcode 162 寻找峰值

发布网友发布时间：2023-01-02 06:51

共1个回答

热心网友时间：2023-10-14 17:20

解法1：
1.分析题意，如果只是判断满足条件的元素，我们可以直接for循环遍历找出满足条件的答案，但是题意要求，必须实现时间复杂度为O(log n) 的算法，目前我们最简单可以想到已知的O(log n) 的算法为二分查找，可是二分查找用于解决已排序的序列是可以的，难道也可以用于解决未排序的序列？显然，答案是可以的
2.满足条件的元素，我们知道一个特征，就是肯定比左右元素大，也就是说满足 nums[index] > nums[index + 1] && nums[index] > nums[index - 1] ，可是如果以这个条件作为二分查找的条件判断，很显然，我们无法进行left、right的回归了，这时，我们需要想办法去精简条件
3.如果 nums[index] > nums[index + 1] 时，证明此时右侧已然满足峰值条件，右侧区间可以舍弃；如果 nums[index] <= nums[index + 1] 时，证明此时是递增的，左侧区间已然满足峰值条件，左侧区间可以舍弃，所以条件可以精简为 nums[mid] > nums[mid + 1] ，而mid为left和right的中间值
这个题目有一个条件需要特别重视，你可以假设 nums[-1] = nums[n] = -∞ ，也就是说无论如何，肯定存在目标峰值，所以才有我们上面的条件去除，反正题目结论是要找其中一个峰值，找到左右侧满足条件时，放心的去找剩余一侧即可。

无