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 思路

??需要在一個先增后減的序列中尋找頂點值，類似爬山的過程，只要一直向上爬，頂點就在前面，身后的路不可能存在頂點，可以通過不斷地拋掉一些區間，來縮小目標范圍。
??之前的題目——第一個壞的版本^[1]中，提到過二分法可以解決形如“ooooxxxx”的問題，本題無法將問題轉化為這種形式，需要從另一個方面來思考，可以將整體拆解成“half half”型的兩半，拋掉其中一半來縮小目標區間。
??使用二分法，取中點，如果中點是從左向右遞增，則可以看成從左向右爬山，當前位置的左邊則不可能存在頂點，拋掉左邊區間；換個方向，如果中點是從右向左遞增，則可以看成是從右向左爬山，當前位置的右邊不可能存在頂點，拋掉右邊區間。

1. 取中點；
2. 比較中點與下一個點的關系是遞增還是遞減，以此來判斷頂點在哪一半區間；
3. 拋掉不可能存在頂點的區間。
4. 繼續對剩下的區間執行以上步驟，直到找到頂點。

??過程中需要判斷當前點的下一步是在向上走還是向下走，考慮下一個元素的時候可能會越界，套用之前的經典二分搜索模板^[2]，則可以不用考慮下一個元素是否越界的問題，因為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 here
        if (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);
        }
    }
}