力扣-剑指Offer II 069题山峰数组的顶部（C++）- 二分+有价值

港控/mmm° 2022-09-16 00:28 118阅读 0赞

题目链接：[https://leetcode-cn.com/problems/B1IidL/][https_leetcode-cn.com_problems_B1IidL]  
题目如下：![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
    public:
        int peakIndexInMountainArray(vector<int>& arr) {
        
            //注：时间复杂度为O(log n),第一时间想到二分
    
            /**
            * 找递增和递减的交换点，可以用二分查找的思想去做
            * 1）若mid周围是递减，那么山峰只可能在前
            * 2）若mid周围是递增，那么山峰只可能在后
            */
            int size=arr.size();
            int low=0,high=size-1;
    
            while(low<high){
        
                int mid=(low+high+1)>>1;
                
                if(arr[mid]>arr[mid-1]) low=mid;
                else high=mid-1;
            }
    
            return low;//arr[low];
        }
    };

[https_leetcode-cn.com_problems_B1IidL]: https://leetcode-cn.com/problems/B1IidL/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b1bfabf87a834e6ebed5b1a64583d3c7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9d65cde660624a8ab92282ceb8a70f9a.png