[LeetCode]162. 寻找峰值（java实现）二分
1. 题目
2. 读题（需要重点注意的东西）
思路（二分）： 1、当nums[i - 1] < nums[i]时： ① 如果从 i - 1 到 n - 1是单调的，那么这条直线单调上升，nums[n - 1] 就是峰值 ② 如果从 i - 1 到 n - 1不是单调的，那么一定存在一个点，使得nums[i] > nums[i + 1]，这个点就是峰值 所以，当nums[i - 1] < nums[i]时，从 i - 1 到 n - 1中，一定存在一个峰值；
2、当nums[i - 1] > nums[i]时：同理可得[0,i−1]中一定包含一个峰值；
由此可知，存在一个性质，能将这段数分为两半，某一边一定有峰值，每次可以将答案区间缩小一半，因此可以使用二分求出这个峰值。
3. 解法
---------------------------------------------------解法---------------------------------------------------
class Solution {
public int findPeakElement(int[] nums) {
int l = 0,r = nums.length - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] > nums[mid+1]) r = mid;
else l = mid + 1;
}
return l;
}
}
可能存在的问题：
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
-
二分
6. 总结
下一篇：
《0-1背包问题》贪心策略