【LeeCode】162. 寻找峰值

【题目描述】

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

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

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

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

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

【示例】

【代码】LeeCode-二分法

在题目描述中出现了 nums[-1] = nums[n] = -∞，这就代表着 只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值

import java.util.*;
// 2023-4-6

class Solution {
    public int findPeakElement(int[] nums) {
         int len = nums.length;
         int left = 0;
         int right = len - 1;
         while (left < right){
             int mid = left + (right - left) / 2;
             if (nums[mid] > nums[mid + 1]){
                 right = mid;
             }else {
                 left = mid + 1;
             }
         }
         return left;
    }
}
public class Main {
    public static void main(String[] args) {
        new Solution().findPeakElement(new int[]{1,2,3,1}); // 输出：2
        new Solution().findPeakElement(new int[]{1,2,1,3,5,6,4}); // 输出：1 或者 5
    }
}

【代码】寻找最大值

import java.util.*;
// 2023-4-6

class Solution {
    public int findPeakElement(int[] nums) {
         int len = nums.length;
         int idx = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[idx]){
                idx = i;
            }
        }
        return idx;
    }
}
public class Main {
    public static void main(String[] args) {
        new Solution().findPeakElement(new int[]{1,2,3,1}); // 输出：2
        new Solution().findPeakElement(new int[]{1,2,1,3,5,6,4}); // 输出：1 或者 5
    }
}

【代码】admin

48 / 65 个通过的测试用例

import java.util.*;
// 2023-4-6

class Solution {
    public int findPeakElement(int[] nums) {
         int len = nums.length;
         if (len < 2) return 0;
         for (int i = 1; i < len - 1; i++){
             if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){
                 return i;
             }

         }
         return -1;
    }
}
public class Main {
    public static void main(String[] args) {
        new Solution().findPeakElement(new int[]{1,2,3,1}); // 输出：2
        new Solution().findPeakElement(new int[]{1,2,1,3,5,6,4}); // 输出：1 或者 5
    }
}