给 n 个整数的山脉数组,即先增后减的序列,找到山顶(最大值)
- 数组严格递增,严格递减
在线评测地址:领扣题库官网
例1:
输入: nums = [1, 2, 4, 8, 6, 3]
输出: 8
例2:
输入: nums = [10, 9, 8, 7],
输出: 10
算法:二分
算法思路
- 由于本题数据是具有部分单调性,我们可以考虑用二分法来解决
- 并且本题保证数组严格递增或严格递减,所以相邻两个数必不相等
- 我们可以通过a[mid]和a[mid+1]的大小关系来判断mid是在左侧还是右侧
代码思路
- 设置左边界等于0,右边界等于numsLen - 1
- 对于mid所指向的数,若nums[mid] > nums[mid + 1]则表示mid指向的数在最大值右侧或最大值,那么right = mid,否则left = mid
- 不断重复 2 直到 left + 1 == right 退出
- left和right指向的数中较大的一个即最大值,将其返回
复杂度分析
N表示数组nums长度
- 空间复杂度:O(N)
- 时间复杂度:O(logN)
public class Solution {
/**
* @param nums: a mountain sequence which increase firstly and then decrease
* @return: then mountain top
*/
public int mountainSequence(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid;
}
}
return Math.max(nums[left], nums[right]);
}
}
更多题解参考:九章官网solution