LeetCode 162. Find Peak Element
2021/7/27 23:36:41
本文主要是介绍LeetCode 162. Find Peak Element,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
题目链接
思路
假设数组长度为N,首先判断0号位置的数和N-1位置的数是不是峰值位置。
0号位置只需要和1号位置比较,如果0号位置大,0号位置就是峰值位置。
N-1号位置只需要和N-2号位置比较,如果N-1号位置大,N-1号位置就是峰值位置。
如果0号位置和N-1在上轮比较中均是最小值,那么数组的样子必然是如下情况:
从0..1是增长
从N-2...N-1是下降
那么峰值位置必在1...N-2之间出现
此时可以通过二分来找峰值位置,先来到中点位置,假设为mid,如果:
arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]
mid位置即峰值位置
否则:
如果趋势是:
则在 1...(mid-1)区间内继续上述二分
如果趋势是:
则在 (mid+1)...(N-2)区间内继续上述二分。
完整代码
public class LeetCode_0162_FindPeakElement { public int findPeakElement(int[] nums) { int n = nums.length; if (n == 1) { return 0; } if (n == 2) { return nums[0] == Math.max(nums[0], nums[1]) ? 0 : 1; } if (nums[n - 1] > nums[n - 2]) { return n - 1; } if (nums[0] > nums[1]) { return 0; } int L = 1; int R = n - 2; while (L <= R) { int mid = L + ((R - L) >> 1); if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) { return mid; } else if (nums[mid] < nums[mid + 1]) { L = mid + 1; } else { R = mid - 1; } } return -1; } }
更多
算法和数据结构笔记
参考资料
- 程序员代码面试指南(第2版)
- 算法和数据结构基础班-左程云
- 极客时间-数据结构与算法之美-王争
- 算法(第四版)
这篇关于LeetCode 162. Find Peak Element的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding