10 寻找山型数组的顶点（Maximum Number in Mountain Sequence）

1 题目

??寻找山型数组的顶点（Maximum Number in Mountain Sequence）

lintcode：题号——585，难度——medium

2 描述

??给定包含n 个整数的山脉数组，即先增后减的序列，找到山顶（最大值），数组严格递增、严格递减。

??样例1：

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

??样例2：

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

3 思路

??需要在一个先增后减的序列中寻找顶点值，类似爬山的过程，只要一直向上爬，顶点就在前面，身后的路不可能存在顶点，可以通过不断地抛掉一些区间，来缩小目标范围。
??之前的题目——第一个坏的版本¹中，提到过二分法可以解决形如“ooooxxxx”的问题，本题无法将问题转化为这种形式，需要从另一个方面来思考，可以将整体拆解成“half half”型的两半，抛掉其中一半来缩小目标区间。
??使用二分法，取中点，如果中点是从左向右递增，则可以看成从左向右爬山，当前位置的左边则不可能存在顶点，抛掉左边区间；换个方向，如果中点是从右向左递增，则可以看成是从右向左爬山，当前位置的右边不可能存在顶点，抛掉右边区间。

1. 取中点；
2. 比较中点与下一个点的关系是递增还是递减，以此来判断顶点在哪一半区间；
3. 抛掉不可能存在顶点的区间。
4. 继续对剩下的区间执行以上步骤，直到找到顶点。

??过程中需要判断当前点的下一步是在向上走还是向下走，考虑下一个元素的时候可能会越界，套用之前的经典二分搜索模板²，则可以不用考虑下一个元素是否越界的问题，因为start或mid之后一定存在end，退出条件是start + 1 < end不会出现访问越界的情况。

3.1 图解

3.2 时间复杂度

??算法的时间复杂度为O(log n)。

3.3 空间复杂度

??算法的空间复杂度为O(1)。

4 源码

??注意事项：

返回的是值，不是序号；

??C++版本：

/**
* @param nums: 参数
* @return: 返回值
*/
int findMin(vector<int> &nums) {int mountainSequence(vector<int> &nums) {// write your code hereif (nums.empty()){return -1;}int start = 0;int end = nums.size() - 1;int mid = 0;while (start + 1 < end){mid = start + (end - start) / 2;if (nums.at(mid) < nums.at(mid + 1)){start = mid;}if (nums.at(mid) > nums.at(mid + 1)){end = mid;}}if (nums.at(start) > nums.at(end)){return nums.at(start);}else{return nums.at(end);}}
}