This is the 15th day of my participation in the genwen Challenge

The title

Arr. Length >= 3 there exists I (0 < I < arr. Length -1) such that:

  • arr[0] < arr[1] < … arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > … > arr[arr.length – 1]

Give you a range array of integers arr, return anything that satisfies arr[0] < ARr [1] <… arr[i – 1] < arr[i] > arr[i + 1] > … > arr[arr.length-1] subscript I.

 

  • Example 1:

Input: arr = [0,1,0] output: 1

  • Example 2:

Input: arr = [0,2,1,0

  • Example 3:

Arr = [0,10,5,2] output: 1

  • Example 4:

Input: arr = [3,4,5,1

  • Example 5:

Input: arr =,69,100,99,79,78,67,36,26,19 [24] output: 2

Tip:

  • 3 <= arr.length <= 104
  • 0 <= arr[i] <= 106

A traversal

Find the first turning point of decline where the index preceding the turning point is the peak

code

class Solution {
    public int peakIndexInMountainArray(int[] arr) {

        for (int i=1; i<arr.length; i++) {if(arr[i]<arr[i-1])
                return i-1;
        }
        return -1; }}Copy the code

dichotomy

Using the problem, we find the following properties: due to the different values of ARR, the left side of the peak element must satisfy strict monotone increasing, while the right side of the peak element must not.

The array is an array of peaks, and the left and right sides of the vertices can be divided into uphill and downhill. Uphill is an ascending array, and downhill is a descending array. Therefore, binary search can be performed under the following conditions:

  • If arr[mid]>arr[mid-1], the current range [l,mid] is an increasing array, so the vertices will only appear in the range [mid+1,r].
  • If arr[mid]

code

class Solution {
    public int peakIndexInMountainArray(int[] arr) {

      int l=1,r=arr.length-2;
      while (l<=r)
      {
          int mid=(r-l)/2+l;
         if(arr[mid]>arr[mid-1])
              l=mid+1;
          else r=mid-1;
      }
      returnr; }}Copy the code