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-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解