稀碎从零算法笔记Day50-LeetCode:寻找峰值

LC50天成就了

题型:数组、滑动窗口、二分

链接:162. 寻找峰值 - 力扣(LeetCode)

来源:LeetCode

题目描述

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

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

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

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

题目样例

示例 1:

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入:nums = 
[1,2,1,3,5,6,4]
输出:1 或 5 
解释:你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

提示:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i

题目思路

滑动窗口就是一次遍历三个元素,单时间复杂度O(N),不满足条件

O(logN)的时间复杂度基本是点名用二分,难点在于如何理解二分:
根据题意,不难看出:如果数组元素严格递增/递减的话,峰值就是末尾/开头
如果是先增后减,那很明显这个【极值点】就是峰值
如果是先减后增,那么两个【边界】都是峰值

那二分的思路就是:从看【mid】和【mid+1】来确定递增递减:①如果递增——即是【mid】<【mid+1】,看就以【mid+1】为左边界;②如果递减——即是【mid】>【mid + 1】,那就以【mid】为有边界
最终left和right相遇是,就找到了极值点

C++代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // 二分
        int len = nums.size();
        if(len == 1)
            return 0;
        int left = -1;
        int right = len -1;
        while(left + 1 < right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] > nums[mid + 1])//如果是一种递增的趋势
                right = mid;//遍历mid的左边,看看有没有递减的趋势
            else//如果是递减的趋势
                left = mid;
        }
        return right;
    }
};

结算页面

相关推荐

  1. 算法笔记Day40-LeetCode:加油站

    2024-04-20 23:26:02       37 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-20 23:26:02       75 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-20 23:26:02       80 阅读
  3. 在Django里面运行非项目文件

    2024-04-20 23:26:02       64 阅读
  4. Python语言-面向对象

    2024-04-20 23:26:02       75 阅读

热门阅读

  1. npm taobao镜像提示 reason: certificate has expired

    2024-04-20 23:26:02       24 阅读
  2. 2-搭建开发环境

    2024-04-20 23:26:02       26 阅读
  3. 自动化_Ansible学习笔记

    2024-04-20 23:26:02       26 阅读
  4. Linux系统安装ansible

    2024-04-20 23:26:02       35 阅读
  5. 系统分析与设计(2)

    2024-04-20 23:26:02       35 阅读
  6. idea错误地commit后如何处理

    2024-04-20 23:26:02       129 阅读