题目简述 LeetCode 852

Let's call an array A a mountain if the following properties hold:

• A.length >= 3
• There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

• 3 <= A.length <= 10000
• 0 <= A[i] <= 10^6
• A is a mountain, as defined above.

解题思路

思路１

• 从前往后依次比较，遇到第一个后者比前者小的，输出前者的下标

思路１

• 折半查找

Code

思路１ -> Code

# include<stdio.h>

int peakIndexInMountainArray(int* A, int ASize) 
{
    int i, index;

    for (i = 0; i < ASize - 1; i ++)
    {
        if(A[i + 1] < A[ i ])
        {
            index = i;
            break;
        }
    }

    return index;
}

int main()
{   
    // int a[10] = {0, 1, 0};
    int a[10] = {0, 2, 1, 0};

    printf("%d \n", peakIndexInMountainArray(a, 4));
}

思路２ -> Code

# include<stdio.h>

int peakIndexInMountainArray(int* A, int ASize) 
{
    int left = 0, right = ASize - 1;
    int mid;
    
    while(left < right)
    {
        mid = left + (right - left) / 2;
        if(A[mid] < A[mid + 1])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }

    return left;
}

int main()
{   
    // int a[10] = {0, 1, 0};
    int a[10] = {0, 2, 1, 0};

    printf("%d \n", peakIndexInMountainArray(a, 4));
}

总结

• 两种思路时间都为 4ms