852. Peak Index in a Mountain Array

發表於 | 分類於

problem

solution

option 1 brute force

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        for(int i=1;i<n-1;++i){
            if(arr[i]>arr[i-1] && arr[i]>arr[i+1]) return i;
        }
        return -1;
        
    }
};

option 2

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        int l = 0, r =n-1;
        while(l+1<n && arr[l] < arr[l+1]) l++;
        return l;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l=0, r = arr.size()-1;
        while(l<r){
            int mid = l + (r-l)/2;
            if(arr[mid]<arr[mid+1]) l = mid+1;
            else r = mid;
        }
        return r;
    }
};

analysis

  • time complexity O(n) O(logn)
  • space complexity O(1)