• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode – sword refers to offer069- the top of the mountain array

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

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]

Given a peak array arR of integers, return any satisfaction

  • arr[0] < arr[1] < … arr[i – 1] < arr[i] > arr[i + 1] > … > arr[arr.length-1] subscript I, i.e. peak top.

 

Example 1:

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

Example 2:

Arr = [1,3,5,4,2] output: 2Copy the code

Example 3:

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

Example 4:

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

Example 5:

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

Tip:

  • 3 <= arr.length <= 104
  • 0 <= arr[i] <= 106
  • The problem data guarantees that the ARR is an array of mountains

 

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

Idea 1: Sequential traversal

  • The sequential traversal is too easy
  • Because it must be an array of peaks so you don’t even have to worry about boundaries
  • The value ranges from 1 to n-1
  • I’m not going to write the code
  • Time complexity O(n)
  • Space complexity O(1)

Idea 2: Binary search

  • We’ve seen in many of the previous dichotomies whether dichotomies are possible or not is not just a question of whether it is necessary but whether it is dichotomous
  • There are two distinct characteristics in this case
    • The left side of the peak element has increasing property
    • The right side of the peak element has a decreasing property
  • So we can start with this as the basis for dichotomous judgment
  • Because it must be a mountain array there must be a peak element
  • So we no longer need to consider the possibility that the boundary is a peak element
  • The dichotomous boundary only needs to consider 1 -> n-1
  • And since there are no identical elements, the boundary shift can be directly +-1
class Solution {
        public int peakIndexInMountainArray(int[] arr) {
            int l = 0, n = arr.length, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (mid == 0) {
                    l = mid + 1;
                    continue;
                }
                if (mid == n - 1) {
                    r = mid - 1;
                    continue;
                }
                if (arr[mid] > arr[mid + 1]) {
                    if (arr[mid] > arr[mid - 1]) {
                        return mid;
                    }
                    r = mid - 1;
                } else {
                    l = mid + 1; }}returnl; }}Copy the code
  • Time complexity O(LGN)
  • Space complexity O(1)
  • Ps: Let’s emphasize again whether the mark of dichotomy can be determined by whether the dichotomy is satisfied
  • Don’t simply judge whether dichotomy is possible based on order
  • And when you’re dealing with LGN time complexity, the first thing you need to think about is divide or divide and conquer
  • You can do dichotomous projects to feel comfortable
  • As for the dichotomous template, you can refer to the three-leaf template to back
  • You can also manually simulate several boundary cases to deepen your understanding