如何做装修网站,wordpress支持的语言包,成都住建局官网查询结果在线验证,在线编辑网页【LeetCode刷题】Day 13 题目1#xff1a;852.山脉数组的峰顶索引思路分析#xff1a;思路1#xff1a;暴力枚举O(N)思路2#xff1a;二分查找O(logN) 题目2#xff1a;162.寻找峰值思路分析#xff1a;思路1#xff1a;二分查找O(logN) 题目1#xff1a;852.山脉数组的… 【LeetCode刷题】Day 13 题目1852.山脉数组的峰顶索引思路分析思路1暴力枚举O(N)思路2二分查找O(logN) 题目2162.寻找峰值思路分析思路1二分查找O(logN) 题目1852.山脉数组的峰顶索引 思路分析
暴力枚举的话就是找单调性越来越大直到找到一个数大于后一个数。这个数就是最大值。 就是单调性相关的问题
思路1暴力枚举O(N)
思路2二分查找O(logN)
二分查找二段性[单调递增(包括峰顶)][单调递减]左区间找右值右边左不变-1就1 代码实现
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left0,rightarr.size()-1;while(leftright){int mid left(right-left1)/2;if(arr[mid]arr[mid-1]) leftmid;else rightmid-1;}return left;}
};LeetCode链接852.山脉数组的峰顶索引 题目2162.寻找峰值 思路分析
这题情况还是比较多递增开始还是递减开始递增开始我们需要找后面比较大的值递减开始说明第一个值就可以。
思路1二分查找O(logN)
不管哪种我们只需要找区间中峰顶的值反正逻辑是一样的下降就找前面增加就找后面不管中间怎么变是这个“山峰”跳到另一个“山峰”反正找到其中一组就可以随着区间不断缩小也会集中在一个“山峰”上。
代码实现
class Solution {
public:int findPeakElement(vectorint nums) {int rightnums.size()-1,left0;while(leftright){ int mid left(right-left1)/2;if(nums[mid]nums[mid-1]) leftmid;else rightmid-1;}return left;}
};LeetCode链接162.寻找峰值
