国庆假期结束，来收收心~

给 n 个整数的山脉数组，即先增后减的序列，找到山顶（最大值）

• 数组严格递增，严格递减

点此在线做题

例 1:

输入: nums = [1, 2, 4, 8, 6, 3]  输出: 8 

例 2:

输入: nums = [10, 9, 8, 7],  输出: 10 

算法：二分

算法思路

• 由于本题数据是具有部分单调性，我们可以考虑用二分法来解决
• 并且本题保证数组严格递增或严格递减，所以相邻两个数必不相等
• 我们可以通过 a[mid]和 a[mid+1]的大小关系来判断 mid 是在左侧还是右侧

代码思路

1. 设置左边界等于 0，右边界等于 numsLen – 1
2. 对于 mid 所指向的数，若 nums[mid] > nums[mid + 1]则表示 mid 指向的数在最大值右侧或最大值，那么 right = mid，否则 left = mid
3. 不断重复 2 直到 left + 1 == right 退出
4. 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]);     } } 

不知道有没有人组个刷题群，互相监督刷题的

大佬有話說 (0)