leetcode 852. Peak Index in a Mountain Array

约定不等于承诺〃 2023-06-22 02:27 29阅读 0赞

[https://leetcode.com/problems/peak-index-in-a-mountain-array/][https_leetcode.com_problems_peak-index-in-a-mountain-array]

给定一个数组，其长度大于等于3并且存在一个0 < i < A.length - 1，使得A\[0\] < A\[1\] < ... < A\[i-1\] < A\[i\] > A\[i+1\] > ... > A\[A.length-1\]

## 一、问题分析 ##

测试用例：

Input: [0,1,0]
    Output: 1
    
    Input: [0,2,1,0]
    Output: 1

从数组的特性可以看出，数组没有重复元素；

问题相当于求数组的最大元素，只需遍历一遍即可。但是，这里数组还有另一个特性，就是以最大元素为分界线，左边部分有A\[i\] < A\[i + 1\]的特性（即升序子数组），右边部分有A\[i\] > A\[i + 1\]的特性（即降序子数组）。

因此，当我们访问任意一个下标mid的元素A\[mid\]时，如果A\[mid\] > A\[mid+1\]，说明mid在下坡路上，峰顶在它的左边。那么mid右边部分也不需要考虑了，剪枝即可，让right = mid（mid有可能就是峰顶）。而如果A\[mid\] < A\[mid + 1\]，说明mid在上坡路上，峰顶在它的右边，那么左边部分也就不用考虑，让left = mid + 1。当left = right时，A\[left\]就是我们要求的峰顶元素了。

## 二、代码实现 ##

class Solution {
        public int peakIndexInMountainArray(int[] A) {
            
            int left = 0, right = A.length - 1;
            
            while (left < right) {
                int mid = left + (right - left) / 2;
                
                if (A[mid] > A[mid + 1]) {
                    right = mid;
                } else {        //A[mid] < A[mid+1]
                    left = mid + 1;
                }
            }
            
            return left;        
        }    
    }

注意，这道题峰顶元素的下标一定是处在非首尾元素的中间位置，所以，才不需要考虑0、A.length-1等边界条件

[https_leetcode.com_problems_peak-index-in-a-mountain-array]: https://leetcode.com/problems/peak-index-in-a-mountain-array/