LeetCode 162.寻找峰值

思路：

1.题目规定了nums[-1] = nums[n] = -∞，也就是假设nums[0]的左边还有一个-∞，nums[n - 1]的右边还有一个-∞。原因在于这样可以保证数组一定有峰值。比如数组是严格递减的，那么nums[0]就是（唯一的）峰值；同理如果数组是严格递增的，那么nums[n - 1]就是（唯一的）峰值。

2.分析：如果i < n - 1且nums[i] < nums[i + 1]，那么在下标[i + 1,n - 1]中一定存在峰值（如果不满足，那么一定有nums[i + 1] < nums[i + 2]，nums[i + 2] < nums[i + 3]，...，nums[n - 1] < nums[n] = -∞，可知不成立，因此在下标[i + 1,n - 1]中一定存在峰值）。同理可知如果i < n - 1且nums[i] > nums[i + 1]，那么在下标[0,i]中一定存在峰值。

3.因此，可以通过二分的方式，通过比较nums[i]和nums[i + 1]的大小关系，不断地缩小存在峰值的范围，二分找到峰值。

4.注意：如果有多个峰值，我们无法在一开始、以及二分过程中就确定哪个峰值最终会成为答案。二分的思路只是不断地缩小范围，并最终找到其中的一个峰值。由于每次只关注mid和mid + 1的局部大小关系，然后根据这个局部信息决定是向左还是向右。不同的数组初始状态会导致算法走向不同的峰值。因此得到的峰值不一定是全局最高峰。

5.复杂度分析：

（1）时间复杂度：O(logn)，其中n为nums的长度。

（2）空间复杂度：O(1)。

附代码：

class Solution { public int findPeakElement(int[] nums) { int left = 0; int right = nums.length - 1; // 闭区间[0,n - 1] while (left < right) { // 此时区间至少还有两个元素 int mid = left + (right - left) / 2; if (nums[mid] > nums[mid + 1]) { // 下坡，峰顶位置 <= mid right = mid; } else { // 上坡，峰顶位置 >= mid + 1 left = mid + 1; } } return left; } }

ACM模式：

import java.util.Scanner; class Solution { public int findPeakElement(int[] nums) { int left = 0; int right = nums.length - 1; // 闭区间[0, n - 1] while (left < right) { // 此时区间至少还有两个元素 int mid = left + (right - left) / 2; if (nums[mid] > nums[mid + 1]) { // 下坡，峰顶位置 <= mid right = mid; } else { // 上坡，峰顶位置 >= mid + 1 left = mid + 1; } } return left; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取数组长度 int n = scanner.nextInt(); // 读取数组元素 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } // 寻找峰值元素 Solution solution = new Solution(); int result = solution.findPeakElement(nums); System.out.println(result); scanner.close(); } }