2023.12.18力扣每日一题

题目来源

力扣每日一题；题序：162

我的题解

方法一 暴力

暴力法需要先排除只有一个元素或者第一个元素满足要求或者最后一个元素满足要求的情况。
然后依次从左到右遍历，先判断是否升序，并记录上升的个数，然后记录转折点，再判断是否降序，并记录下降的个数，最后根据上升的个数和下降的个数判断是不是峰值。

时间复杂度：O(n)。需要遍历一遍数组
空间复杂度：O(1)

class Solution {
    public int findPeakElement(int[] nums) {
        int n=nums.length;
        if(n==1||nums[0]>nums[1])
            return 0;
        if(nums[n-1]>nums[n-2])
            return n-1;
        int i=1;
        while(i<n){
            int up=1;
            int down=1;
            // 判断升序
            while(i<n&&nums[i]>nums[i-1]) {
                up++;
                i++;
            }
            // 记录转折点
            int res=i-1;
            // 判断降序
            while(i<n&&nums[i]<nums[i-1]) {
                down++;
                i++;
            }
            if(up>1&&down>1)
                return res;
        }
        return 0;
    }
}

方法二 二分查找

这道题可以直接进行二分查找，不过要注意边界的考虑。

1. mid在数据范围(0,n-1)里，并且满足nums[mid]>num[mid-1]&&nums[mid]>nums[mid+1]，则mid就是峰值，直接返回；
2. mid=0，并且满足nums[mid]>nums[mid+1]，则mid是峰值，直接返回；
3. mid=n-1,并且满足nums[mid]>nums[mid-1]，则mid是峰值，直接返回；
4. 当nums[mid]<nums[mid+1],则需要抛弃[l,mid]的范围，在剩余的[mid+1,r]范围内继续搜索；
5. 其他条件需要抛弃[mid,r]范围，子啊剩余的[l,mid-1]范围内继续搜索

时间复杂度：O(logn)。二分查找需要的时间
空间复杂度：O(1)

class Solution {
    public int findPeakElement(int[] nums) {
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=left+((right-left)>>1);
            //条件1
            if(mid>0&&mid<nums.length-1&&nums[mid-1]<nums[mid]&&nums[mid+1]<nums[mid]){
                return mid;
                //条件2
            }else if(mid==0&&nums[mid+1]<nums[mid]){
                return mid;
                //条件3
            }else if(mid==nums.length-1&&nums[mid-1]<nums[mid]){
                return mid;
                //条件4
            }else if((mid>0&&mid<nums.length-1&&nums[mid-1]>=nums[mid])||
                        (mid==nums.length-1&&nums[mid-1]>=nums[mid])){
                right=mid-1;
                //条件5
            }else {
                left=mid+1;
            }
        }
        return left;
    }
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~