Leetcode -852- Peak index of the mountain array

[Blog link]

A path to learning at 🐔

The nuggets home page

[B].

An array arR that matches the following properties is called a mountain array: arr.length >=3I (0 < i < arr.length - 1) makes: arr[0] < arr[1] <... arr[i-1] < arr[i] 
 arr[i] > arr[i+1] >... > arr[arr.length -1] gives you a range array of integers arr, returns anything that satisfies arr[0] < arr[1] <... arr[i -1] < arr[i] > arr[i + 
1] >... > arr[arr.length -1] subscript I. The sample1: Input: arr = [0.1.0] output:1The sample2: Input: arr = [0.2.1.0] output:1The sample3: Input: arr = [0.10.5.2] output:1The sample4: Input: arr = [3.4.5.1] output:2The sample5: Input: arr = [24.69.100.99.79.78.67.36.26.19] output:2Tip:3 <= arr.length <= 104 
 0 <= arr[i] <= 106Question data guarantees that ARR is a mountain array progression: it is easy to think of a time complexity O(n) solution, can you design an O(log(n)) solution? Related Topics Binary Search 👍173 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Violence method time complexity O(n)

Idea 2: Binary search

• The difference between the binary search in the previous two problems is that this time it’s based on monotonicity rather than size
• The mountain element needs to be monotonically decreasing to the right and monotonically increasing to the left
• The problem data guarantees that the ARR is an array of mountains so you don’t need to consider special cases or dissatisfy cases

public int peakIndexInMountainArray(int[] arr) {
            int l = 0, r = arr.length - 1;
            while (l < r) {
                int mid = (r - l)/2 + l;
                if (mid > 0 && mid <= arr.length - 2) {
                    // The mountain element is to the left of mid
                    if (arr[mid] > arr[mid + 1]) {
                        // Meet the mountain element condition
                        if (arr[mid] > arr[mid - 1]) {
                            return mid;
                        }
                        // Contains the mountain element (element to the right of the mountain element)
                        else{ r = mid; }}// The mountain element is to the right of mid
                    else {
                        l = mid + 1; }}}return l;
        }
Copy the code

Time complexity O(LGN)

Idea three: three points to find (refer to the palace water greatly)

• Specifically, because the peak element is the global maximum
• Therefore, we can divide the current interval into **[L, M1], [M1, m2] and [m2, r]** each time
• Arr [m1] > ARR [m2]
• It indicates that the peak element cannot exist in [m2, r] and let r = m2-1. The other interval analysis does the same thing

public int peakIndexInMountainArray(int[] arr) {
            int n = arr.length;
            int l = 0, r = n - 1;
            while (l < r) {
                int m1 = l + (r - l) / 3;
                int m2 = r - (r - l) / 3;
                if (arr[m1] > arr[m2]) {
                    r = m2 - 1;
                } else {
                    l = m1 + 1; }}return r;
        }
Copy the code

Time complexity O(
$lg_3^n$)