“This is the second day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

Title description:

852. Peak Index of Mountain Array – LeetCode (leetcode-cn.com)

An array ARR that matches the following properties is called a mountain array:

  • arr.length >= 3
  • There areI (0 < I < arr. Length - 1)Make:
    • 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.

The sample a

Input: arr = [0,1,0] output: 1Copy the code

Example 2

Input: arr = [0,2,1,0Copy the code

Example 3

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

Example 4

Input: arr = [3,4,5,1Copy the code

The sample of five

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

Tip:

  • 3 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^6
  • Subject data guaranteearrIt’s an array of mountains

Thought analysis

traverse

Subject of a image, if we put the array subscript as x, value as y, add an array to the coordinate system, then the array is presented the appearance of the shape of a mountain, is simply increasing in the former period, and then the next period of decline, and the topic request peak index, is to find the largest value in the array.

This is pretty easy, we just have to go through it.

When we traverse to subscript II, if we have arri−1

arri+1\textit{arr}_{i-1} < \textit{arr}_i > \textit{arr}_{I +1}arri−1

arri+1, So ii is the subscript we need to find.

And we can optimize it a little bit, because our peak, it’s always increasing, I don’t know how much, but after the peak, the next one is definitely decreasing, So we just need to find I that satisfies arri>arri+1\textit{arr}_i > \textit{arr}_{I +1}arri>arri+1.

AC code

class Solution {
    fun peakIndexInMountainArray(arr: IntArray): Int {
        var ans = -1
        for(i in 0..arr.size-1) {
            if(arr[i] > arr[i+1]) {
                ans = i
                break}}return ans
    }
}
Copy the code

Binary search

From the previous analysis, we know that the peak element is the global maximum, so it is natural for us to use dichotomy to find it.

AC code

class Solution {
    fun peakIndexInMountainArray(arr: IntArray): Int {
        var left = 0
        var right = arr.size - 1

        while (left < right) {
            val mid = (left + right + 1) ushr 1
            if (arr[mid - 1] > arr[mid]) {
                right = mid - 1
            } else {
                left = mid
            }
        }
        return left
    }
}
Copy the code

conclusion

Return the index of the maximum value, or find it.

reference

Mountain Array Peak Index – Mountain Array peak Index – LeetCode (leetcode-cn.com)

Peak Index in a Mountain Array – LeetCode (leetcode-cn.com)