This is the 29th day of my participation in Gwen Challenge

Peak Index of Mountain Array (Item no. 852)

The title

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

  • arr.length >= 3
  • There arei(0 < i < arr.length - 1) :
    • 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
Copy the code

Example 2:

Input: arr = [0.2.1.0] output:1
Copy the code

Example 3:

Input: arr = [0.10.5.2] output:1
Copy the code

Example 4:

Input: arr = [3.4.5.1] output:2
Copy the code

Example 5:

Input: arr = [24.69.100.99.79.78.67.36.26.19] output:2
Copy the code

Tip:

  • 3 <= arr.length <= 104
  • 0 <= arr[i] <= 106
  • Subject data guaranteearrIt’s an array of mountains

Advanced: It is easy to think of time complexity O(n) solutions, can you design an O(log(n)) solution?

link

Leetcode-cn.com/problems/pe…

explain

This one, this is a classic dichotomy.

You can actually see the answer at first glance, just go through it once, and I won’t explain it.

Dichotomy a little explanation, a little variation.

Mid +1 = mid+1 = mid+1 = mid+1 = mid+1 = mid+1 = mid+1 = mid+1

So the key here is to find the first number that’s bigger than the next number, and that’s the mountain.

And they say there can only be one peak, and it can’t be on either side, which simplifies things even more.

Update left and right values in time.

Your own answer (traversal)

var peakIndexInMountainArray = function(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > arr[i + 1]) return i
  }
};
Copy the code

A simple for loop, one step in place, performance is not bad, time and memory are more than 80%, close to 90% of that kind.

My own answer (dichotomy)

var peakIndexInMountainArray = function(arr) {
  var left = 1
      right = arr.length - 2
  while (left <= right) {
    var mid = ~~((left + right) / 2)
    if (arr[mid] < arr[mid + 1]) {
      left = mid + 1
    } else {
      right = mid - 1}}return left
};
Copy the code

The logic of dichotomy has been covered in the explanation section, but there is one more point to note.

The iteration termination condition here is 👇 :

left <= right
Copy the code

According to? Because the key factor of each iteration here is mid, it is possible to have the same situation of left and right, if the condition is 👇 :

left < right
Copy the code

So it’s possible that the mid is missing, so the condition here needs to be <=.

Everything else is normal. Ordinary dichotomy.

Your own answers (in order)

The peak is the maximum value of the array. The peak is the maximum value of the array.

The maximum value is easy to do, and the first element of the array is the mountain.

Iterate through the array again, find index and return.

var peakIndexInMountainArray = function(arr) {
  var max = [...arr].sort((a, b) = > b - a)[0]
  return arr.findIndex(val= > val === max)
};
Copy the code

The time complexity is not very high.

The main problem is a little strange, it should be the best performance, but in fact not, can only hover around 60% to 70%, and whether sorting or traversal, are above 80%, a little confused.

A better way

There is no





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)

If you are interested, you can also check out my personal homepage at 👇

Here is RZ