leetcode 162. Find Peak Element | 162. 寻找峰值（二分法找局部最大值）

蔚落 2023-01-23 08:55 146阅读 0赞

## 题目 ##

[https://leetcode.com/problems/find-peak-element/][https_leetcode.com_problems_find-peak-element]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

##### 2021-7-21 16:28:31 更新版思路： #####

> 根据左神在 [**课上**][Link 1] 说的，可以使用二分法找到局部最小值，看上升或下降坡度，则有点类似于罗尔定理的感觉。同理，也可以用二分找到局部最大值，具体可以参考本题 [**英文版官方题解**][Link 2] 或 [**中文版图解**][Link 3].  
> 罗尔定理：如果 R 上的函数 f(x) 满足以下条件：  
> （1）在闭区间 \[a,b\] 上连续  
> （2）在开区间 (a,b) 内可导  
> （3）f(a)=f(b)  
> 则至少存在一个 ξ∈(a,b)，使得 f’(ξ)=0。  
> 实际上，当我们找到一个上升沿的时候，可以推断它的右边必然有一个山峰，如果没有的话，它就是最后一个上升沿，而最后一个上升沿的右端点，或者第一个下降沿的左端点也是山峰。  
> ![在这里插入图片描述][723f9d01d88567189efdf36b3f24779b.png]  
> 不严谨的证明过程，不保证正确…可以参考一下：  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

class Solution { 
        public int findPeakElement(int[] nums) { 
            int L = 0,R = nums.length - 1;
            while(L < R){ 
                int M = L + ((R - L) >> 1);
                if(nums[M] > nums[M+1]) R = M;
                else L = M+1;
            }
            return L;
        }
    }

--------------------

##### 写题时的原思路 #####

看题目要求是 O(log n)，想到每次删一半，但是写完之后才发现并不符合要求。。先将错就错吧，后面有空再完善下。

第一次比较次数为 n/2，第二次比较次数为 n/4，第三次8/n，…，总比较次数为 n/2+n/4+n/8+n/16+…= ?

根据《算法导论》“同时找最大最小元素的最小比较次数”的原理，也是每次删一半，即不重复的两两比较。

所以每次淘汰一半后，最后剩下的是最大值，也就是 Peak Element。

class Solution { 
        public int findPeakElement(int[] nums) { 
            ArrayList<Integer> list = new ArrayList<>();
            ArrayList<Integer> index = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                list.add(nums[i]);
                index.add(i);
            }
            while (list.size() != 1) { 
                ArrayList<Integer> newList = new ArrayList<>();
                ArrayList<Integer> newIndex = new ArrayList<>();
                for (int i = 0; i < list.size() - 1; i += 2) {  // 两两比较，每次扔掉一半
                    if (list.get(i) > list.get(i + 1)) { 
                        newList.add(list.get(i));
                        newIndex.add(index.get(i));
                    } else { 
                        newList.add(list.get(i + 1));
                        newIndex.add(index.get(i + 1));
                    }
                }
                if (list.size() % 2 == 1) {  // 奇数个数情况，简单起见，末尾元素无条件进入下一轮判断
                    newList.add(list.get(list.size() - 1));
                    newIndex.add(index.get(index.size() - 1));
                }
                list = newList;
                index = newIndex;
            }
            return index.get(0);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_find-peak-element]: https://leetcode.com/problems/find-peak-element/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221004/6b97bb4b3631437aacb6b19f2e799009.png
[Link 1]: https://ke.qq.com/webcourse/index.html#cid=3067253&term_id=103187834&taid=10471954904436085&type=1024&vid=5285890809662945662
[Link 2]: https://leetcode.com/problems/find-peak-element/solution/
[Link 3]: https://leetcode-cn.com/problems/find-peak-element/solution/yi-zhang-tu-yi-ju-hua-jie-jue-er-fen-fan-mzig/
[723f9d01d88567189efdf36b3f24779b.png]: /images/20221004/6ea6c12c39454bc1891a76254b937d68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221004/1e9bcfbb34db45d288740a9c34a05a19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/103008450672497886c132d00df4e3ad.png