【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值

简介: 【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值

题目1:852.山脉数组的峰顶索引

思路分析:

暴力枚举的话就是找单调性,越来越大,直到找到,一个数大于后一个数。这个数就是最大值。

就是单调性相关的问题

思路1:暴力枚举O(N)

思路2:二分查找O(logN)

二分查找:二段性:[单调递增(包括峰顶)][单调递减],左区间找右值,右边左不变,-1就+1

代码实现:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left=0,right=arr.size()-1;
        while(left<right)
        {
            int mid =left+(right-left+1)/2;
            if(arr[mid]>arr[mid-1]) left=mid;
            else right=mid-1;
        }
        return left;
    }
};

LeetCode链接:852.山脉数组的峰顶索引


题目2:162.寻找峰值

思路分析:

这题情况还是比较多,递增开始,还是递减开始,递增开始我们需要找后面比较大的值,递减开始,说明第一个值就可以。

思路1:二分查找O(logN)

不管哪种,我们只需要找区间中峰顶的值,反正逻辑是一样的,下降就找前面,增加就找后面,不管中间怎么变,是这个“山峰”跳到另一个“山峰”,反正找到其中一组就可以,随着区间不断缩小,也会集中在一个“山峰”上。

代码实现

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int right=nums.size()-1,left=0;
        while(left<right)
        {   
            int mid = left+(right-left+1)/2;
            if(nums[mid]>nums[mid-1]) left=mid;
            else right=mid-1;
        }
        return left;
    }
};

LeetCode链接:162.寻找峰值

相关文章
|
2天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
10天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
6 0
|
14天前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
13 0
|
14天前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
12 0
|
14天前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
13 0
|
28天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
28天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
29天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
29天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
29天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板