Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
Topic describes
An array ARR that matches the following properties is called a mountain array:
- 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] output: 1
Example 3: input: arr = [0,10,5,2] output: 1
Example 4: input: arr = [3,4,5,1] output: 1
Example 5: input, output arr =,69,100,99,79,78,67,36,26,19 [24] : 1
Train of thought
The mountain array is very visual, and basically it has a unique maximum value, which is monotonously decreasing to the left and to the right, just like a mountain.
The intuitive way is to start from the left and find the first value arr[k]>arr[k+1], so k is our solution. This way, the time is order len.
Considering the above method, there is one condition that is underutilized: after the maximum value occurs, the array decreases monotonically. Considering the dichotomy, arR [mid] can be divided into two cases:
- arr[mid] > arr[mid+1]
Mid indicates that mid is either the peak of the mountain or the downhill value behind it. The current MID can be used as an alternative, and then continue to bisect to the left
- arr[mid] < arr[mid+1]
It indicates that mid must be an ascending slope before the summit, the summit must be on the right, and continue to bisect to the right
Java version code
class Solution { public int peakIndexInMountainArray(int[] arr) { int index = 0; int left = 1, right = arr.length-2; while (left <= right) { int mid = left + ((right - left)>>1); if (arr[mid] > arr[mid+1]) { index = mid; right = mid - 1; } else { left = mid + 1; } } return index; }}Copy the code