162. Find Peak Element

https://leetcode.com/problems/find-peak-element/

给定一个无序数组，且nums[i] != nums[i+1]，找出其中的peak元素，即比左右两边的元素都要大的元素，可以假设nums[-1] 和nums[n]都是负无穷，如果存在多个peak,只需要返回一个就行
------------------------------------------------------------------------------------------------------------------------------------
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
-------------------------------------
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.

1. Sequential Search

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i] < nums[i-1])// 前面都是顺序，只要出现一个逆序对就是peak
                return i-1;
        }
        return nums.size()-1;//如果前面全部都是顺序，那么最后一个数与倒数第二个较小的数以及虚拟的负无穷组成peak.
    }
};

提交结果

Runtime: 4 ms, faster than 96.57% of C++ online submissions for Find Peak Element.
Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Find Peak Element.

2. 递归减治

class Solution {
public:
    int decrease_conquer(vector<int>& nums, int lo, int hi)
    {
        if (lo==hi)
            return lo;
        int mi = (lo + hi)>>1;
        if(nums[mi]<nums[mi+1])
            return decrease_conquer(nums, mi+1, hi);
        else 
            return decrease_conquer(nums, lo, mi);
    }
    int findPeakElement(vector<int>& nums) {
        return decrease_conquer(nums, 0, nums.size()-1);
    }
};

提交结果

Runtime: 4 ms, faster than 96.57% of C++ online submissions for Find Peak Element.
Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Find Peak Element.

3. 迭代减治

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int lo = 0, hi = nums.size()-1;
        while(lo < hi)
        {
            int mi = (lo + hi)>>1;
            if(nums[mi]<nums[mi+1])
                lo=mi+1;
            else
                hi=mi;
        }
        return lo;
    }
};

提交结果

Runtime: 4 ms, faster than 96.57% of C++ online submissions for Find Peak Element.
Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Find Peak Element.

-----------------------------------------------------------------------------------------------------------------------------
关于其可以使用减治来代替分治的的原因:
按理来说，在这个无序数组中，峰值可能存在左边，也可能存在右边，为什么这里可以只选择左边或者右边就可以实现？

• 首先明确一点，对于 nums[i]!=nums[i-1]的数组，肯定是存在峰值元素的，可以尝试构建如下：
  __ ___ ___ ___ ___
  1 2 __ ___ ___ 2 1 (This makes sure that the corner element is not the answer)
  1 2 3 4 ___ 4 3 2 1 (Just trying to put answer away from corner)
  1 2 3 4 5 4 3 2 1 (But at one time i will have to put a number which is the peak since) SINCE NO ADJACENT SAME ALLOWED
• 我们在nums[mi]<nums[mi+1]时，执行 lo = mi+1,此后可以发现，lo 是大于 lo -1的，也就是说，从 lo -1 到 lo 是一个上升趋势
• 由于不存在 nums[i]==nums[i+1] 的情况，因此另外一种情况就是，nums[mi]>nums[mi+1]，我们执行 hi=mi，此后可以发现，hi (此时已经等于 mi)是大于 hi + 1 (此时为 mi +1)的，因此从 hi 到 hi + 1 是一个下降趋势
• 最后，从 lo -1 到 lo ，再到 hi 到 hi + 1 是一个先上升后下降的趋势，因此肯定存在峰值，当迭代循环到 lo 和 hi 相等时，lo-1 --> lo(hi) --> lo +1(hi+1)，就是一个先上升后下降的过程，因此，lo 就是峰值所在。

此段讨论结果来自与小伙伴 肖同学 的讨论。